@inproceedings{1debba55b230490093eaf10a22a737d5,

title = "On Streaming Algorithms for Geometric Independent Set and Clique",

abstract = "We study the maximum geometric independent set and clique problems in the streaming model. Given a collection of geometric objects arriving in an insertion only stream, the aim is to find a subset such that all objects in the subset are pairwise disjoint or intersect respectively. We show that no constant factor approximation algorithm exists to find a maximum set of independent segments or 2-intervals without using a linear number of bits. Interestingly, our proof only requires a set of segments whose intersection graph is also an interval graph. This reveals an interesting discrepancy between segments and intervals as there does exist a 2-approximation for finding an independent set of intervals that uses only O(α(I) log | I| ) bits of memory for a set of intervals I with α(I) being the size of the largest independent set of I. On the flipside we show that for the geometric clique problem there is no constant-factor approximation algorithm using less than a linear number of bits even for unit intervals. On the positive side we show that the maximum geometric independent set in a set of axis-aligned unit-height rectangles can be 4-approximated using only O(α(R) log | R| ) bits.",

keywords = "Geometric independent set, Streaming algorithms, Geometric intersection graphs, Communication lower bounds",

author = "Jelle Oostveen and Fabian Klute and Sujoy Bhore",

note = "Funding Information: Fabian Klute supported by the Austrian Science Foundation (FWF) grant J4510. Jelle Oostveen is partially supported by the NWO grant OCENW.KLEIN.114 (PACAN). Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.",

year = "2022",

month = oct,

day = "21",

doi = "10.48550/arXiv.2207.01108",

language = "English",

isbn = "978-3-031-18366-9",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "211--224",

editor = "Parinya Chalermsook and Bundit Laekhanukit",

booktitle = "Approximation and Online Algorithms",

edition = "1",

}