Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles

Monika Henzinger, Stefan Neumann, Andreas Wiese

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 worst-case 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 d-dimensional hypercubes we maintain a (1 + ε)2d-approximate solution in the unweighted case and a O(2d)-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 d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1 + ε) logd1 N.

Original languageEnglish
Title of host publication36th International Symposium on Computational Geometry, SoCG 2020
EditorsSergio Cabello, Danny Z. Chen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771436
DOIs
Publication statusPublished - 1 Jun 2020
Event36th International Symposium on Computational Geometry, SoCG 2020 - Zurich, Switzerland
Duration: 23 Jun 202026 Jun 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume164
ISSN (Print)1868-8969

Conference

Conference36th International Symposium on Computational Geometry, SoCG 2020
Country/TerritorySwitzerland
CityZurich
Period23/06/2026/06/20

Bibliographical note

Funding Information:
Funding Monika Henzinger: The research leading to these results has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement No. 340506. Stefan Neumann: Part of this work was done while visiting Brown University. Stefan Neumann gratefully acknowledges the financial support from the Doctoral Programme “Vienna Graduate School on Computational Optimization” which is funded by the Austrian Science Fund (FWF, project no. W1260-N35). The research leading to these results has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013) / ERC grant agreement No. 340506. Andreas Wiese: Andreas Wiese was supported by the grant Fondecyt Regular 1170223.

Publisher Copyright:
© Monika Henzinger, Stefan Neumann, and Andreas Wiese; licensed under Creative Commons License CC-BY 36th International Symposium on Computational Geometry (SoCG 2020).

Keywords

  • Approximation algorithms
  • Dynamic algorithms
  • Geometric intersection graphs
  • Independent set
  • Interval graphs

Cite this