On streaming algorithms for geometric independent set and clique

DOI10.1007/978-3-031-18367-6_11MaRDI QIDQ6176560zbMATH OpenOpenAlexFDO

Authors Sujoy Bhore, Fabian Klute, Jelle J. Oostveen

Publication date 25 July 2023

Published in Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.01108

zbMATH Keywords

communication lower boundsgeometric independent setgeometric intersection graphsstreaming algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

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(alpha(mathcalI)log|mathcalI|)$ bits of memory for a set of intervals $mathcalI$ with $alpha(mathcalI)$ being the size of the largest independent set of $mathcalI$. 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(alpha(mathcalR)log|mathcalR|)$ bits.

Cites work

• A unified approach to approximating resource allocation and scheduling
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Approximation algorithms for maximum independent set of pseudo-disks
• Computing the independence number of intersection graphs
• Coresets in dynamic geometric data streams
• Data streams: algorithms and applications.
• Dynamic algorithms for monotonic interval scheduling problem
• Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles
• Finding a Maximum Clique in an Arbitrary Graph
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• Independent set of intersection graphs of convex objects in 2D
• Independent sets in vertex-arrival streams
• Label placement by maximum independent set in rectangles
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Reducibility among combinatorial problems
• Scheduling Split Intervals
• Space-constrained interval selection
• Streaming Algorithms for Independent Sets
• Streaming geometric optimization using graphics hardware
• The space complexity of approximating the frequency moments
• Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
• Worst-Case Efficient Dynamic Geometric Independent Set

Cited in

(9)

• Streaming Algorithms for Smallest Intersecting Ball of Disjoint Balls
• Streaming Algorithms for Independent Sets
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Interval selection in data streams: weighted intervals and the insertion-deletion setting
• Random-order online independent set of intervals and hyperrectangles
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Dynamic streaming algorithms for geometric independent set
• Deterministic independent sets in the semi-streaming model

This page was built for publication: On streaming algorithms for geometric independent set and clique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176560)