Projects per year
Abstract
Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect. We present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worstcase update times that are polylogarithmic for constant d and ε > 0, assuming that the coordinates of all input objects are in [0, N] ^{d} and each of their edges has length at least 1. We obtain the following results: For weighted intervals, we maintain a (1 + ε)approximate solution. For ddimensional hypercubes we maintain a (1 + ε)2 ^{d}approximate solution in the unweighted case and a O(2 ^{d})approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1 + ε)approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds. For weighted ddimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1 + ε) log ^{d}− ^{1} N.
Original language  English 

Title of host publication  36th International Symposium on Computational Geometry (SoCG 2020) 
Editors  Sergio Cabello, Danny Z. Chen 
ISBN (Electronic)  9783959771436 
DOIs  
Publication status  Published  2020 
Event  36th International Symposium on Computational Geometry (SoCG 2020)  Zürich, Switzerland Duration: 22 Jun 2020 → 26 Jun 2020 https://socg20.inf.ethz.ch 
Conference
Conference  36th International Symposium on Computational Geometry (SoCG 2020) 

Country/Territory  Switzerland 
City  Zürich 
Period  22/06/20 → 26/06/20 
Internet address 
Austrian Fields of Science 2012
 102031 Theoretical computer science
Keywords
 Approximation algorithms
 Dynamic algorithms
 Geometric intersection graphs
 Independent set
 Interval graphs
Projects
 2 Finished

Vienna Graduate School on Computational Optimization
Pflug, G., Stelzer, V., Henzinger, M., Bot, R. I., Bomze, I., Schichl, H., Neumaier, A., Raidl, G. R., Scarinci, T., Geiersbach, C., Gabl, M., Böhm, A., Nguyen, D. K., Kimiaei, M., Neumann, S., Djukanovic, M., Horn, M., Glanzer, M., Birghila, C., Brandstätter, G., Luipersbeck, M., Meier, D., Ponleitner, B., Goranci, G., Kahr, M., Klocker, B. & Hungerländer, P.
1/03/16 → 29/02/20
Project: Research funding

GraphAlgApp: Challenges in Graph Algorithms with Applications
Henzinger, M., FrolikSteffan, U. & Licayan, C.
1/03/14 → 31/08/19
Project: Research funding