Online Algorithms for Geometric Independent Set
This work provides tight bounds and improved algorithms for the online independent set problem on geometric graphs, addressing a fundamental problem in online algorithms with practical implications for resource allocation and scheduling.
The paper studies the online maximum independent set problem, proving that a simple greedy algorithm achieves a competitive ratio equal to the independent kissing number ζ, which is optimal for deterministic and asymptotically optimal for randomized algorithms. For geometric settings with known representations, they present randomized algorithms with improved expected competitive ratios that are strictly better than deterministic lower bounds for unit ball graphs in ℝ³ and polylogarithmic in diameter ratios for fat objects and hyper-rectangles.
In the classical online model, the maximum independent set problem admits an $Ω(n)$ lower bound on the competitive ratio even for interval graphs, motivating the study of the problem under additional assumptions. We first study the problem on graphs with a bounded independent kissing number $ζ$, defined as the size of the largest induced star in the graph minus one. We show that a simple greedy algorithm, requiring no geometric representation, achieves a competitive ratio of $ζ$. Moreover, this bound is optimal for deterministic online algorithms and asymptotically optimal for randomized ones. This extends previous results from specific geometric graph families to more general graph classes. Since this bound rules out further improvements through randomization alone, we investigate the power of randomization with access to geometric representation. When the geometric representation of the objects is known, we present randomized online algorithms with improved guarantees. For unit ball graphs in $\mathbb{R}^3$, we present an algorithm whose expected competitive ratio is strictly smaller than the deterministic lower bound implied by the independent kissing number. For $α$-fat objects and for axis-aligned hyper-rectangles in $\mathbb{R}^d$ with bounded diameters, we obtain algorithms with expected competitive ratios that depend polylogarithmically on the ratio between the maximum and minimum object diameters. In both cases, the randomized lower bound implied by the independent kissing number grows polynomially with the ratio between the maximum and minimum object diameters, implying substantial performance guarantees for our algorithms.