Abstract
We study the Maximum Independent Set problem for geometric objects given in the data stream model. A set of geometric objects is said to be independent if the objects are pairwise disjoint. We consider geometric objects in one and two dimensions, i.e., intervals and disks. Let α be the cardinality of the largest independent set. Our goal is to estimate α in a small amount of space, given that the input is received as a onepass stream. We also consider a generalization of this problem by assigning weights to each object and estimating β, the largest value of a weighted independent set. We initialize the study of this problem in the turnstile streaming model (insertions and deletions) and provide the first algorithms for estimating α and β.
For unitlength intervals, we obtain a (2+ε)approximation to α and β in poly(log(n)/ε) space. We also show a matching lower bound. Combined with the 3/2approximation for insertiononly streams by Cabello and PerezLanterno [Cabello and PérezLantero, 2017], our result implies a separation between the insertiononly and turnstile model. For unitradius disks, we obtain a (8√3/π)approximation to α and β in poly(log(n)/ε) space, which is closely related to the hexagonal circle packing constant.
Finally, we provide algorithms for estimating α for arbitrarylength intervals under a bounded intersection assumption and study the parameterized space complexity of estimating α and β, where the parameter is the ratio of maximum to minimum interval length.
BibTeX  Entry
@InProceedings{bakshi_et_al:LIPIcs:2020:12667,
author = {Ainesh Bakshi and Nadiia Chepurko and David P. Woodruff},
title = {{Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {64:164:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12667},
URN = {urn:nbn:de:0030drops126679},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.64},
annote = {Keywords: Weighted Maximum Independent Set, Geometric Graphs, Turnstile Streams}
}
Keywords: 

Weighted Maximum Independent Set, Geometric Graphs, Turnstile Streams 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) 
Issue Date: 

2020 
Date of publication: 

11.08.2020 