arxiv: 2604.14677 · v1 · submitted 2026-04-16 · 💻 cs.CG · cs.DS

Recognition: unknown

Online Algorithms for Geometric Independent Set

Minati De, Satyam Singh

Authors on Pith no claims yet

Pith reviewed 2026-05-10 08:41 UTC · model grok-4.3

classification 💻 cs.CG cs.DS

keywords algorithmsboundgeometricindependentratiocompetitiveonlinediameters

0 comments

The pith

A greedy online algorithm achieves optimal competitive ratio ζ for independent set on bounded-kissing-number graphs, while randomized geometric algorithms yield polylog-competitive ratios for unit balls in R^3 and α-fat objects.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Online algorithms must decide on each arriving item immediately without knowing what comes next. For selecting a large set of non-overlapping geometric objects such as balls or rectangles, the paper defines the independent kissing number as the largest number of objects that can all touch one central object without touching each other. A basic greedy rule that accepts an object only if it does not overlap previously accepted ones guarantees a competitive ratio matching this number. When the actual shapes and positions are known in advance, randomized methods can beat the basic bound, achieving guarantees that grow only logarithmically with the range of object sizes rather than polynomially.

Core claim

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. ... we present randomized online algorithms with improved guarantees. For unit ball graphs in R^3, we present an algorithm whose expected competitive ratio is strictly smaller than the deterministic lower bound implied by the independent kissing number.

Load-bearing premise

The input graphs have bounded independent kissing number ζ (or, for the improved bounds, that the algorithm is given the geometric representation of the objects and that the objects satisfy fatness or bounded-diameter conditions).

Figures

Figures reproduced from arXiv: 2604.14677 by Minati De, Satyam Singh.

**Figure 1.** Figure 1: Points of Λ are drawn. Here ℓ1 = 4 + δ, and ℓ2 = 2√ 3. The projections of planes Pℓ2 and P0, P−ℓ2 over a rectangular region are depicted, where Pk denotes the plane parallel to xy plane with z-coordinate value k. There is no lattice point in between any of these two planes. Properties of the lattice: Lemma 10. The distance between any two distinct points in the lattice Λ is strictly greater than 4. Proof. … view at source ↗

**Figure 2.** Figure 2: Illustration of Claim 13. The box R is decomposed into R0 and its translate R1 along the x1-axis. If a corner of R coincides with a lattice point in Λ (where Λ denotes the set of lattice points), then the construction ensures that both R0 and R1 have corners that also coincide with lattice points. The black points denote lattice points in the plane at z = 0, while red points denote the lattice points in th… view at source ↗

read the original abstract

In the classical online model, the maximum independent set problem admits an $\Omega(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 $\zeta$, 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 $\zeta$. 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 $\alpha$-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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean ζ-competitive greedy algorithm for any graph with bounded independent kissing number, proves it tight for deterministic online algorithms, and then uses geometry to get strictly better randomized ratios in concrete cases like unit balls in R^3.

read the letter

The main thing to know is that a basic greedy algorithm achieves competitive ratio exactly equal to the independent kissing number ζ on any graph where that number is bounded, and the bound is optimal for deterministic algorithms. The same ζ is asymptotically tight for randomized algorithms in the pure graph setting, but geometry lets them beat it with randomization when the embedding is known upfront. This extends earlier results that were limited to specific families like intervals or disks to a broader class defined only by the kissing number, without needing coordinates for the basic result. The charging argument is standard: each selected vertex blocks at most ζ vertices from the optimum, with a clean case split when the selected vertex is in the optimum. The lower bound via adaptive adversary (present a center, then its ζ neighbors) is simple and works for the general case. For the geometric improvements, the unit-ball algorithm in R^3 uses positional information to set randomization probabilities so the expected ratio drops below ζ. The polylog-diameter-ratio bounds for α-fat objects and bounded-diameter hyper-rectangles in R^d replace the polynomial dependence that the kissing number forces, which is a concrete gain. The soft spots are limited. The improved ratios require the geometric representation to be given, which is explicit in the model but narrows the setting. The diameter ratio can still be large in the worst case, so the polylog is better than polynomial but not constant. No circularity or load-bearing gaps appear in the sketched arguments. This paper is for researchers in online algorithms and computational geometry who care about independent set on intersection graphs or packing problems. A reader working on competitive analysis with geometric structure will find the separation between graph-only and geometry-aided results useful. It deserves a serious referee because the core claims organize the landscape and the randomized improvements are specific enough to check in detail. I would send it to peer review.

Referee Report

2 major / 3 minor

Summary. The paper studies the online maximum independent set problem on graphs with bounded independent kissing number ζ (the size of the largest induced star minus one). It shows that a simple greedy algorithm (select a vertex if it does not conflict with previously selected ones) achieves competitive ratio exactly ζ without requiring geometric representation. This ratio is optimal for deterministic online algorithms (via an adaptive adversary that forces acceptance of a center followed by ζ independent neighbors) and asymptotically optimal for randomized algorithms (consistent with Ω(ζ/log ζ) lower bounds via Yao's principle). With access to geometric representation, the paper gives randomized algorithms with strictly better expected ratios for unit balls in R^3 and polylogarithmic dependence on the max/min diameter ratio for α-fat objects and bounded-diameter axis-aligned hyper-rectangles in R^d, both of which beat the polynomial growth of the kissing-number lower bound in the diameter ratio.

Significance. If the charging arguments, adversary constructions, and geometric randomization schemes hold, the work meaningfully generalizes prior results on specific geometric families (e.g., intervals, disks) to the broader class of graphs with bounded independent kissing number while cleanly separating the power of geometry from pure randomization. The explicit optimality proofs for the deterministic case and the demonstration that geometry enables ratios below the kissing-number barrier are concrete strengths.

major comments (2)

[§3] §3 (greedy analysis): the charging argument claims each selected vertex covers at most ζ vertices of OPT, with the special case that a selected vertex in OPT covers only itself. Verify that the definition of independent kissing number (α(N(v)) ≤ ζ) is applied uniformly when the selected vertex belongs to OPT and has no neighbors in OPT; any overcounting here would invalidate the exact 1/ζ ratio.
[§5] §5 (unit balls in R^3): the randomized algorithm claims an expected ratio strictly smaller than the deterministic lower bound implied by the kissing number. The improvement relies on positional information to set randomization probabilities; confirm that the analysis accounts for all possible overlaps under the unit-ball geometry and that the strict inequality holds for every instance, not merely in expectation over a restricted distribution.

minor comments (3)

[Abstract] Abstract and §2: the phrase 'asymptotically optimal for randomized ones' should be accompanied by an explicit statement of the Ω(ζ/log ζ) lower bound reference or construction to avoid ambiguity.
[§2] Notation: ensure that the independent kissing number ζ is defined identically in the general-graph section and in the geometric sections (e.g., for fat objects); minor inconsistencies in the 'minus one' clause appear in early definitions.
[Figures] Figures: the diagrams illustrating the adversary construction for deterministic optimality and the positional randomization for unit balls would benefit from clearer labeling of selected vs. rejected vertices.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and for the detailed, constructive comments. We address each major comment below with clarifications. Minor revisions will be made to improve readability where appropriate.

read point-by-point responses

Referee: [§3] §3 (greedy analysis): the charging argument claims each selected vertex covers at most ζ vertices of OPT, with the special case that a selected vertex in OPT covers only itself. Verify that the definition of independent kissing number (α(N(v)) ≤ ζ) is applied uniformly when the selected vertex belongs to OPT and has no neighbors in OPT; any overcounting here would invalidate the exact 1/ζ ratio.

Authors: We thank the referee for highlighting this point. In the charging scheme of §3, every vertex of OPT is charged to exactly one vertex of the algorithm's solution ALG. If an ALG vertex v is not in OPT, then because OPT is independent the vertices of OPT charged to v must lie in N(v) and form an independent set; by definition of the independent kissing number we have α(N(v)) ≤ ζ, so at most ζ such vertices are charged to v. If v belongs to OPT, then (again because OPT is independent) v has no neighbors in OPT, so v is charged only by itself. This special case is already covered by the uniform bound “at most ζ” and introduces no overcounting. Consequently |OPT| ≤ ζ |ALG| holds for every input, giving the exact competitive ratio ζ. We will insert a short clarifying sentence in the revised manuscript to make the handling of the OPT-in-ALG case explicit. revision: yes
Referee: [§5] §5 (unit balls in R^3): the randomized algorithm claims an expected ratio strictly smaller than the deterministic lower bound implied by the kissing number. The improvement relies on positional information to set randomization probabilities; confirm that the analysis accounts for all possible overlaps under the unit-ball geometry and that the strict inequality holds for every instance, not merely in expectation over a restricted distribution.

Authors: The analysis in §5 does account for all possible overlaps permitted by unit-ball geometry in R^3. Randomization probabilities are computed from the known centers; the expectation calculation then uses the fact that any two unit balls intersect in a region whose volume is bounded by a constant strictly less than the volume of a single ball. This geometric constant yields a per-vertex expectation factor strictly better than 1/ζ. The resulting bound E[ALG] ≥ OPT / r with r < ζ holds for every fixed input sequence (the expectation is solely over the algorithm’s coins). No restriction to a special distribution of inputs is required; the guarantee is worst-case over inputs. We therefore confirm that the claimed strict improvement is valid as stated. revision: no

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation is self-contained. The competitive ratio of ζ follows from a standard charging argument that directly invokes the definition of the independent kissing number (maximum size of an induced star minus one, equivalently α(N(v)) ≤ ζ for every v): each ALG vertex is charged with at most ζ OPT vertices (itself if it belongs to OPT, or its independent neighbors in OPT otherwise), and every OPT vertex is adjacent to at least one ALG vertex or belongs to ALG. The deterministic lower bound is witnessed by the same star graph that realizes ζ, and the randomized asymptotic lower bound is obtained via Yao's principle on bipartite graphs respecting the same α(N(v)) ≤ ζ bound. The geometric improvements exploit positional information to refine selection probabilities and are compared against the general-graph lower bound; none of these steps reduces to a self-definition, a fitted parameter renamed as a prediction, or a load-bearing self-citation. The analysis therefore rests on independently verifiable combinatorial facts rather than circular re-use of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from graph theory and online competitive analysis; the independent kissing number is explicitly defined in the abstract as the size of the largest induced star minus one. No free parameters are fitted, no new entities are postulated, and no ad-hoc axioms beyond classical graph and algorithm concepts are required.

axioms (1)

standard math Standard definitions of online competitive ratio, independent set, and induced subgraphs in undirected graphs.
Invoked throughout the competitive analysis and lower-bound arguments.

pith-pipeline@v0.9.0 · 5549 in / 1280 out tokens · 20422 ms · 2026-05-10T08:41:32.391984+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

25 extracted references

[1]

Approximation schemes for inde- pendent set and sparse subsets of polygons.J

Anna Adamaszek, Sariel Har-Peled, and Andreas Wiese. Approximation schemes for inde- pendent set and sparse subsets of polygons.J. ACM, 66(4):29:1–29:40, 2019

2019
[2]

Allan Borodin and Ran El-Yaniv.Online computation and competitive analysis.Cambridge University Press, 1998

1998
[3]

url: http://www.cs.toronto.edu/ bor/2420s19/papers/draft-ch1-8.pdf, DRAFT: March 14, 2019, 2019

Allan Borodin and Denis Pankratov.Online Algorithms. url: http://www.cs.toronto.edu/ bor/2420s19/papers/draft-ch1-8.pdf, DRAFT: March 14, 2019, 2019

2019
[4]

Favrholdt, Michal Kotrbc´ ık, and Kim S

Joan Boyar, Lene M. Favrholdt, Michal Kotrbc´ ık, and Kim S. Larsen. Relaxing the irre- vocability requirement for online graph algorithms.Algorithmica, 84(7):1916–1951, 2022

1916
[5]

Fishkin, Christos Kaklamanis, and Evi Papaioannou

Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, and Evi Papaioannou. Ran- domized on-line algorithms and lower bounds for computing large independent sets in disk graphs.Discret. Appl. Math., 155(2):119–136, 2007. 16

2007
[6]

Maximum independent set of rectangles

Parinya Chalermsook and Julia Chuzhoy. Maximum independent set of rectangles. In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 892–901. SIAM, 2009

2009
[7]

Chan and Sariel Har-Peled

Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum inde- pendent set of pseudo-disks.Discret. Comput. Geom., 48(2):373–392, 2012

2012
[8]

On-line maximum independent set in chordal graphs.Foundations of Computing and Decision Sciences, 30(4), 2005

George Christodoulou and Vassilis Zissmopoulos. On-line maximum independent set in chordal graphs.Foundations of Computing and Decision Sciences, 30(4), 2005

2005
[9]

Independent sets in vertex-arrival streams

Graham Cormode, Jacques Dark, and Christian Konrad. Independent sets in vertex-arrival streams. InProceedings of the 46th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 132 ofLIPIcs, pages 45:1–45:14, 2019

2019
[10]

Online geometric covering and piercing.Algorithmica, pages 1–27, 2024

Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh. Online geometric covering and piercing.Algorithmica, pages 1–27, 2024

2024
[11]

Online dominating set and coloring for geometric intersection graphs.Comput

Minati De, Sambhav Khurana, and Satyam Singh. Online dominating set and coloring for geometric intersection graphs.Comput. Geom., 134:102256, 2026

2026
[12]

Mark de Berg, Arpan Sadhukhan, and Frits C. R. Spieksma. Stable approximation algo- rithms for dominating set and independent set.SIAM J. Discret. Math., 39(2):921–945, 2025

2025
[13]

Independence and coloring problems on intersection graphs of disks

Thomas Erlebach and Jir´ ı Fiala. Independence and coloring problems on intersection graphs of disks. InEfficient Approximation and Online Algorithms - Recent Progress on Classical Combinatorial Optimization Problems and New Applications, volume 3484 ofLNCS, pages 135–155. Springer, 2006

2006
[14]

Polynomial-time approximation schemes for geometric intersection graphs.SIAM J

Thomas Erlebach, Klaus Jansen, and Eike Seidel. Polynomial-time approximation schemes for geometric intersection graphs.SIAM J. Comput., 34(6):1302–1323, 2005

2005
[15]

Garey and David S

Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979

1979
[16]

Random-order online independent set of intervals and hyperrectangles

Mohit Garg, Debajyoti Kar, and Arindam Khan. Random-order online independent set of intervals and hyperrectangles. InProceedings of the 32nd European Symposium on Algorithms, (ESA), volume 308 ofLIPIcs, pages 58:1–58:18, 2024

2024
[17]

Online independent set beyond the worst-case: Secretaries, prophets, and pe- riods

Oliver G¨ obel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold V¨ ocking. Online independent set beyond the worst-case: Secretaries, prophets, and pe- riods. InProceedings of the 41st International Colloquium on Automata, Languages, and Programming, (ICALP), Part II, volume 8573 ofLNCS, pages 508–519. Springer, 2014

2014
[18]

Halld´ orsson, Kazuo Iwama, Shuichi Miyazaki, and Shiro Taketomi

Magn´ us M. Halld´ orsson, Kazuo Iwama, Shuichi Miyazaki, and Shiro Taketomi. Online independent sets.Theor. Comput. Sci., 289(2):953–962, 2002

2002
[19]

Reducibility among combinatorial problems

Richard M Karp. Reducibility among combinatorial problems. InProceedings of the sym- posium on the Complexity of Computer Computations, pages 85–103, 1972

1972
[20]

Lipton and Andrew Tomkins

Richard J. Lipton and Andrew Tomkins. Online interval scheduling. InProceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 302–311, 1994

1994
[21]

Marathe, H

Madhav V. Marathe, H. Breu, Harry B. Hunt III, S. S. Ravi, and Daniel J. Rosenkrantz. Simple heuristics for unit disk graphs.Networks, 25(2):59–68, 1995. 17

1995
[22]

Joseph S. B. Mitchell. Approximating maximum independent set for rectangles in the plane. InProceedings of the 62nd Symposium on Foundations of Computer Science, (FOCS), pages 339–350. IEEE, 2021

2021
[23]

The problem of the twenty-five spheres.Russian Mathematical Surveys, 58(4):794, 2003

Oleg Rustumovich Musin. The problem of the twenty-five spheres.Russian Mathematical Surveys, 58(4):794, 2003

2003
[24]

Vazirani.Approximation algorithms

Vijay V. Vazirani.Approximation algorithms. Springer, 2001

2001
[25]

Probabilistic computations: Toward a unified measure of complexity (extended abstract)

Andrew Chi-Chih Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract). InProceedings of the 18th Symposium on Foundations of Computer Science, (FOCS), pages 222–227. IEEE Computer Society, 1977. 18

1977