Pith. sign in

REVIEW 2 major objections 5 minor 74 references

The paper proves that many geometric families — disks, pseudodisks, fat rectangles, similar-size fat triangles, 3D unit cubes — beat the 1−1/e barrier in polynomial time, in both unweighted and budgeted max coverage.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-03 12:31 UTC pith:LQGWBCL5

load-bearing objection The black-box reduction from DIS to max coverage is the real contribution and looks correct; the main risk is the application list, where the linear 2-shallow cell premise needs checking for some headline families. the 2 major comments →

arxiv 2607.29160 v1 pith:LQGWBCL5 submitted 2026-07-31 cs.CG cs.CCcs.DS

Approximation Algorithms for Geometric Maximum Coverage

Sujoy Bhore , Timothy M. Chan , Pasin Manurangsi This is my paper
classification cs.CG cs.CCcs.DS MSC 68W2568U05
keywords geometric maximum coverageapproximation algorithmsLP rounding2-shallow cell complexitydiscrete independent setbudgeted coverageVC dimensionmax-volume selection
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The paper asks when geometric structure lets the maximum coverage problem beat the universal 1−1/e approximation barrier. It proves that any set system with linear 2-shallow cell complexity — covering pseudodisks, fat axis-aligned rectangles, similar-size fat triangles, and 3D unit cubes, among others — admits a polynomial-time algorithm with approximation factor 1−1/e+Ω(1), including the weighted (budgeted) version. The engine is Theorem 3.2, a black-box reduction showing that any LP-relative O(1)-approximation for the max-weight discrete independent set problem can be converted into a (1−1/e+Ω(1/C²))-approximation for max coverage. The paper also improves the parameterized scheme for small k under bounded VC dimension, gives an EPTAS for continuous max-volume selection of fat convex objects, and adds several new hardness results.

Core claim

The central claim is that geometry provides a systematic escape from the 1−1/e ceiling: for any family of objects with linear 2-shallow cell complexity, weighted max coverage is polynomially approximable to factor 1−1/e+Ω(1). The proof is a black-box reduction (Theorem 3.2): if the max-weight discrete independent set problem on the same family can be approximated to within a factor C of its own LP optimum, then weighted max coverage can be approximated to (1−1/e+Ω(1/C²))OPT_LP, minus the single-object maximum (removable by a standard lemma). Because linear 2-shallow cell complexity yields such a DIS approximation with C=O(1) — re-derived in Appendix A from a known LP-rounding argument — the

What carries the argument

Linear 2-shallow cell complexity: for any finite subcollection of objects, the number of distinct subsets of objects induced by points lying in exactly two objects is at most a linear function of the number of objects. This abstract count lets a known LP-rounding method for max-weight discrete independent set achieve a constant factor C; the paper's Theorem 3.2 then converts the DIS oracle into a max coverage algorithm with factor 1−1/e+Ω(1/C²). The conversion works by partitioning the LP solution into 'good' objects (near-average marginal coverage) and extracting a large independent set among them, which seeds a greedy run with a guaranteed head start.

Load-bearing premise

The load-bearing premise is the Appendix A counting step asserting that linear 2-shallow cell complexity bounds the number of exactly-two witness cells (without which the DIS approximation and the Ω(1) gain collapse), with two secondary fragile points: the Appendix C Minkowski-expansion volume bound for the EPTAS, and the AI-drafted geometric case analyses in the hardness section, which call for independent verification.

What would settle it

Compute the 2-shallow cell complexity of the dual set systems used for max hitting set over pseudodisks or 3D halfspaces: a subfamily with superlinear pairwise-witness count would break the dual corollaries. Alternatively, test Fact 5.2 by brute force on small random sets of α-fat convex objects, comparing vol(∪(s⊕B_{ε diam s})) with (1+cε) vol(∪s) for tiny ε — a violation would invalidate the continuous EPTAS.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Weighted and budgeted max coverage now beats 1−1/e in polynomial time for pseudodisks, fat rectangles, similar-size fat triangles, 3D unit cubes, and other families — the first such guarantees for many of them.
  • The reduction transfers to max hitting set and max dominating set, giving the same 1−1/e+Ω(1) factor for weighted hitting set over disks/pseudodisks, 3D halfspaces, 3D unit cubes, and for weighted dominating set over disks/pseudodisks.
  • For constant VC dimension and small k, a (1−ε)-approximation for max coverage runs in 2^{O((dk/ε) log(dk/ε))} poly time, improving the previous 2^{O(dk²/ε⁵)} bound and widening the PTAS regime.
  • The continuous max-volume version admits an EPTAS for fat convex objects in constant dimension (2^{O(1/ε^{2d})} poly time) and a (1−1/e+Ω(1))-approximation for homothets of O(1) convex objects.
  • Hardness results complement the algorithms: APX-hardness for fat rectangles and related classes, (1−1/e+ε)-hardness for boxes in dimension growing with 1/ε, and exclusion of n^{poly(1/ε)}-time PTAS for 3D box volumes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The black-box shape of Theorem 3.2 invites a bootstrap: a better DIS approximation derived from a better max coverage approximation on the same family could amplify the Ω(1) gain toward the hardness limit; the paper does not explore this loop.
  • The 2-shallow cell complexity hypothesis may be reducible to an LP-level condition, such as a bound on total pairwise LP mass in the DIS relaxation, which would export the result to non-geometric set systems with bounded 'conflict density'.
  • The small-k scheme's greedy-and-guess recursion is generic enough that similar 2^{O((dk/ε) log(dk/ε))} bounds may carry to other bounded-VC coverage problems, such as partial set cover or budgeted hitting set.
  • The Appendix A counting step and Appendix C volume bound are the technical hinges; the manuscript's disclosure that two proofs in the hardness section were drafted with AI assistance marks those geometric case analyses as the natural place for independent re-derivation before building on the hardness results.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies geometric maximum coverage. Its main contribution is a general LP-rounding reduction: given any LP-relative O(1)-approximation for max-weight discrete independent set (DIS), one obtains a (1−1/e+Ω(1))-approximation for weighted geometric max coverage, beating the classical 1−1/e barrier. The reduction is stated as Theorem 3.2 and combined with Lemma 2.3 (a re-derivation of Chan–Har-Peled for families with linear 2-shallow cell complexity) to yield Corollary 3.4 for many geometric families. The paper also gives a parameterized approximation scheme for bounded VC dimension with running time 2^{O((dk/ε) log(dk/ε))}, an EPTAS for continuous max-volume selection for fat convex objects, and several hardness results, including APX-hardness for various rectangle families and a low-dimensional hardness construction for max-volume selection based on a box-path embedding.

Significance. If correct, the paper would be a significant qualitative advance: it unifies geometric max coverage with geometric set cover and DIS, showing that geometry helps break the 1−1/e barrier for the same families where O(1)-approximations are known for those other problems. The Section 3 reduction is elegant and appears internally sound, and the parameterized scheme genuinely simplifies and improves the previous BKL algorithm. The paper also ships full proofs of key primitives (Appendix A), openly discloses AI assistance for two proofs, and provides extensive hardness complementing the upper bounds. The main concern is whether the geometric application list in Corollary 3.4 is fully supported, and whether a numerical inconsistency in the low-dimensional hardness construction undermines that theorem as written.

major comments (2)
  1. [§2, Lemma 2.3 and §3, Corollary 3.4] The bridge from the black-box Theorem 3.2 to the geometric families is the assumption f_2(n)=O(n) for linear 2-shallow cell complexity. Corollary 3.4 asserts that every family in (i) has linear union complexity, citing [APS05], and hence linear f_2. This is not established for 2D fat rectangles: the standard union-complexity bound for axis-aligned fat rectangles is Θ(n log n), not O(n), and the manuscript gives no direct bound on f_2(n) for this family. Since Lemma 2.3's DIS approximation factor is Θ(1/c) with c from f_2(n)≤cn, a superlinear f_2 would make the Ω(1/C^2) gain in Theorem 3.2 vanish. The same caution applies to 'similar-height rectangles.' The authors should supply per-family proofs or citations for f_2(n)=O(n), or remove the unsupported entries. (I do not share the skeptic's example of 3D halfspaces: the union of halfspaces is the complement of a convex set, so its union co
  2. [§6.1.2, proof of Theorem 6.8] The proof sets K=2·10^6 n^3 and later bounds a segment length by '3Kn≤6·10^6 n^3'. With the stated K, 3Kn=6·10^6 n^4, and a typical segment length (e.g., H_j−K u for u=1, j≈3n/2) is Θ(Kn)=Θ(n^4). Lemma 6.6 requires D≤2^L, and with L=4⌈log₂ n⌉+20 we have 2^L≈2^20 n^4, which is smaller than the Θ(n^4) constants above. Thus the constructed path may violate the Single-Axis Box Path hypothesis, so the proof of Theorem 6.2's low-dimensional hardness does not go through as written. The fix is likely local (take K=Θ(n^2) to match the displayed O(n^3) bound), but this needs correction before the hardness claim is sound.
minor comments (5)
  1. [§3, proof of Theorem 3.2, line 2] The algorithm defines h as the smallest index satisfying the inequality in line 2, but does not specify the case where no such h exists. If no h exists, the greedy solution already achieves t_k≤e^{-(1+δ)}OPT_LP, i.e., a (1−1/e+Ω(δ))-approximation, so the algorithm should explicitly return the greedy solution in that case.
  2. [Appendix A] In the expectation lower bound, the expression '1−∑ δys′' should be '1−∑ ys′/b' (or define δ=1/b). This is a minor typographical issue.
  3. [Appendix C, Fact 5.2] The containment claim 'p⊕B_{εr} ⊆ (1+C_{d,α}ε)τ' is plausible but compressed. Please expand the justification that the cone of directions from p to the inner ball contains d vectors from V with pairwise angle at least Ω_{d,α}(1) while keeping τ homothetic to τ_0 and contained in s.
  4. [§5, Lemma 5.3] The running-time notation '2^{O(2^d b)}' is ambiguous. If the number of choices of Z is 2^{2^{db}}, the exponent should be 2^{O(2^{db})} (or better, the final theorem's 2^{O(1/ε^{2d})} makes clear the intended dependence). Please clarify the notation.
  5. [§3, Corollary 3.4] The list in (i) includes both '2D fat rectangles' and '2D similar-size fat rectangles'. If the former is meant to be 'similar-size', please correct the entry; if genuinely arbitrary-size fat rectangles are intended, the f_2(n)=O(n) issue in the major comment applies.

Circularity Check

0 steps flagged

No significant circularity: the central reduction is self-contained and the geometric premises are cited from independent work.

full rationale

The paper's main theorem (Theorem 3.2) is an explicit black-box reduction: it assumes an LP-relative C-approximation for max-weight discrete independent set and derives a (1-1/e+Omega(1/C^2)) approximation for weighted max coverage. The analysis is carried out entirely in Section 3 and does not reuse the theorem it is proving; the only external input is the DIS guarantee. That input is supplied by Lemma 2.3, whose proof is re-derived in full in Appendix A from the definition of 2-shallow cell complexity rather than imported from the cited [CH12] paper. Appendix A's Clarkson-Shor counting argument is a derivation, not a restatement of the conclusion, and no fitted parameter is later renamed as a prediction. Corollary 3.4's family list rests on the external combinatorial-geometry survey [APS05] and [MPS+94]; whether every listed family truly has linear union complexity is a correctness/verification concern, not a circularity. Fact 5.2, used in the EPTAS, is proved in Appendix C, and the shifting lemma is a standard prior lemma, not an unverified self-citation invoked to force the result. Hardness results are reductions from external theorems (Feige, Chan-Grant, Chlebik-Chlebikova). The paper contains no self-definitional step, no fitted-input-called-prediction step, and no uniqueness claim imported from the authors' own prior work. The acknowledged small quantitative constant is an analysis detail and does not indicate that the result reduces to its own assumptions. Therefore the derivation chain is self-contained relative to its stated geometric hypotheses, and no circularity is exhibited.

Axiom & Free-Parameter Ledger

6 free parameters · 11 axioms · 0 invented entities

All listed entries are either proof-analysis constants or external theorems — there is no experimental data in this paper. The free parameters are hand-chosen constants that an instantiation would need to fix; none is fitted to data. The axioms are the external hardness theorems (Feige; Chan–Grant; Chlebík–Chlebíková), standard VC-dimension tools (ε-approximations, Sauer–Shelah), the shifting lemma, and the combinatorial-geometry facts (union complexity ⇒ shallow cell complexity) connecting abstract conditions to concrete shape families. No new physical or structural entities are postulated; the reduction gadgets (boxes encoding set systems; the box-paths) are standard computational constructions.

free parameters (6)
  • δ (and δ′ = 5δ) = Θ(1/C); C = DIS approximation constant
    Hand-chosen analysis slack in Theorem 3.2; the proof requires δ small (δ < 1/6) and derives γ < 3δ. Only the existence of a small δ matters, so the claim does not depend on its numeric value.
  • ε_ℓ = 2/(ℓ+2); δ_ℓ = ε_{ℓ−1}ε_ℓ/4 = 1/((ℓ+1)(ℓ+2)) = determined by the recurrence in Section 4
    Recursion-depth and approximation-size parameters in the FPT-AS, chosen so the error recurrence ε_ℓ = ε_{ℓ−1}(1−ε_ℓ/2) telescopes. Any schedule with the same asymptotics works.
  • b = ⌈log(L/ε)⌉; L ≈ d/ε, odd, L > d = as stated in Section 5
    Quadtree rounding depth and shift-grid granularity in the EPTAS; chosen so 2^{−(λ_s+b)} ≤ ε·diam(s), placing rounded cells inside the ε-expanded objects.
  • L = 4⌈log₂ n⌉ + 20; s = 6L + 6; K = 2·10⁶ n³ = as stated in Theorem 6.8
    Subdivision length, box-path length, and grid spacing in the box embedding; chosen to satisfy the segment-distance inequalities 100·2^{L/2} ≤ D ≤ 2^L.
  • γ = 1/512 (heavy-intersection constant); α ∈ [2,4] = 1/512
    Fixed by the box-path construction in Lemma 6.6: consecutive intersection volume is 1/(128α) ≥ 1/512 for α ≤ 4. Any constant would propagate; 1/512 is this construction's value.
  • ℓ₀ = 1, ℓ₁ = 2 (Theorem 6.1 interval lengths) = ratio 2
    Interval-length ratio in the high-dimensional max-volume reduction; the gap is Ω((r−1)/(r³−1)) = Ω(1) for r = 2. Any constant r > 1 works.
axioms (11)
  • domain assumption Feige's max coverage hardness with bounded set size c and bounded frequency f (Thm 6.15; property asserted in footnote 12)
    Input to Theorem 6.14: (1−1/e+ε)-hardness for unit boxes in dimension d = 2cf. The bounded-frequency property is asserted, not proved.
  • domain assumption Chan–Grant APX-hardness for geometric set cover with set size ≤ 3 (Thm 6.13)
    Together with the new Lemma 6.12, this is the basis for the APX-hardness list in Theorem 6.11.
  • domain assumption Max-IS on degree-3 graphs is NP-hard to approximate; s-subdivision gap-transfer formula; box-intersection embeddability of subdivisions (Thms 6.9, 6.10 from [CC03, CC05])
    External hardness backbone for Theorem 6.8 (box embedding) and Theorem 6.2 (log-hardness for max-volume selection).
  • domain assumption Chan's shifted-quadtree shifting lemma (Lemma 5.5, cited to [Cha03])
    Invoked without proof in Section 5; load-bearing for the EPTAS: each object is 2L-aligned for all but at most d shifts.
  • domain assumption Linear union complexity ⇒ linear ℓ-shallow cell complexity for the object families (Clarkson–Shor; [APS05]; [MPS+94, Thm 1.3])
    Instantiates Corollary 3.4: the geometric families satisfy the abstract condition of the main theorem via these external combinatorial-geometry bounds.
  • standard math Existence and construction of δ-approximations of size O((D/δ²) log(D/δ)) for VC-dim-D set systems (Fact 4.2 [BCM99])
    Used in the FPT-AS (Section 4) to approximate the greedy-covered region A_G.
  • standard math Sauer–Shelah lemma: number of distinct traces |S|_R| = O(|R|^d)
    Bounds the number of guessed signatures in the FPT-AS running time.
  • standard math Near-linear-time Δ-edge-coloring of bipartite multigraphs (Cole–Ost–Schirra, Lemma 6.7)
    Provides the coordinate assignment A(v,e) used to route subdivided edges in the box embedding.
  • standard math Hardy–Littlewood-type maximal bound and the geometric covering claim used in Fact 5.2's proof (Appendix C)
    The maximal step cites [Ste93]; the covering step — every fat convex s contains a homothetic copy τ of a fixed fat parallelepiped with a vertex at a given point p — is asserted without detailed proof.
  • standard math 2-shallow-cell-complexity counting principle for witness pairs (Appendix A)
    The key step in the re-derivation of Lemma 2.3: |Ψ_t| ≤ c|{s∈bR : w_s ≥ t}|, i.e. pairs of selected objects that share a 2-shallow cell are bounded by the cell-complexity constant times the number of selected objects.
  • standard math Greedy colorability of the element-conflict graph with Δ = cf colors (Theorem 6.14)
    Each element shares a set with at most f(c−1) elements, so a greedy coloring with cf colors exists; used to encode set systems as boxes.

pith-pipeline@v1.3.0-daily-deepseek · 32965 in / 41132 out tokens · 322470 ms · 2026-08-03T12:31:50.486554+00:00 · methodology

0 comments
read the original abstract

We study the maximum coverage problem for geometric set systems: given a set of points, a set of geometric objects, and a number $k$, select $k$ objects maximizing the number of points inside their union. - We present a polynomial-time approximation algorithm with approximation factor strictly better than $1-1/e$ for any set system with linear 2-shallow cell complexity (or any set system that can be decomposed into a constant number of such set systems). The result also holds for the weighted maximum coverage problem, where objects have weights and we want to select objects with total weight within a given budget. The result applies to many types of geometric objects, including pseudodisks in 2D, fat axis-aligned rectangles in 2D, similar-size fat triangles in 2D, axis-aligned unit cubes in 3D. - For small $k$, we obtain a $(1-\epsilon)$-approximation algorithm more generally for any set system with constant VC dimension, running in time exponential in $\tilde{O}(k/\epsilon)$. This simplifies and improves Badanidiyuru, Kleinberg, and Lee's parameterized approximation scheme [SoCG'12] running in time exponential in $\tilde{O}(k^2/\epsilon^5)$. - A continuous version of the geometric maximum coverage problem asks for $k$ objects maximizing the volume of their union. We give better approximation algorithms for this problem for certain families of objects; e.g., we obtain an EPTAS for fat convex objects in any constant dimension. - We complement our algorithms with several hardness results, e.g., APX-hardness for fat axis-aligned rectangles in 2D, $(1-1/e+\epsilon)$-approximation hardness for axis-aligned boxes in a dimension dependent on $\epsilon$, and a lower bound ruling out $n^{\mathop{\rm poly}(1/\epsilon)}$-time PTASs for the continuous problem for axis-aligned boxes in 3D.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

74 extracted references · 15 canonical work pages

  1. [1]

    Karl Bringmann and Sergio Cabello and Michael T. M. Emmerich , title =. 33rd International Symposium on Computational Geometry (SoCG) , _series =. 2017 , doi =

    2017

  2. [2]

    Chan , title =

    Timothy M. Chan , title =. 54th Annual. 2013 , url =

    2013

  3. [3]

    53rd International Colloquium on Automata, Languages, and Programming,

    Sujoy Bhore and Subhash Suri and Jie Xue and Xiongxin Yang and Jiumu Zhu , title =. 53rd International Colloquium on Automata, Languages, and Programming,

  4. [4]

    Overmars and Chee

    Mark H. Overmars and Chee. New Upper Bounds in Klee's Measure Problem , journal =. 1991 , doi =

    1991

  5. [5]

    Proceedings of the 11th Annual conference on Genetic and evolutionary computation , pages=

    Investigating and exploiting the bias of the weighted hypervolume to articulate user preferences , author=. Proceedings of the 11th Annual conference on Genetic and evolutionary computation , pages=

  6. [6]

    Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation , pages=

    Two-dimensional subset selection for hypervolume and epsilon-indicator , author=. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation , pages=

    2014

  7. [7]

    Proceedings of the twenty-fourth annual symposium on Computational geometry , pages=

    A (slightly) faster algorithm for Klee's measure problem , author=. Proceedings of the twenty-fourth annual symposium on Computational geometry , pages=

  8. [8]

    Evolutionary Computation , volume=

    An efficient algorithm for computing hypervolume contributions , author=. Evolutionary Computation , volume=. 2010 , publisher=

    2010

  9. [9]

    Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem , journal =

    G. Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem , journal =. 1980 , doi =

    1980

  10. [10]

    Fisher and George L

    Marshall L. Fisher and George L. Nemhauser and Laurence A. Wolsey , title =. Oper. Res. , volume =. 1979 , doi =

    1979

  11. [11]

    On Approximability of Clustering Problems Without Candidate Centers , booktitle =

    Vincent Cohen. On Approximability of Clustering Problems Without Candidate Centers , booktitle =. 2021 , doi =

    2021

  12. [12]

    Ashwinkumar Badanidiyuru and Robert Kleinberg and Hooyeon Lee , title =. Proc. 28th. 2012 , doi =

    2012

  13. [13]

    and Shor, Peter W

    Clarkson, Kenneth L. and Shor, Peter W. , journal=. Applications of Random Sampling in Computational Geometry,. 1989 , doi =

    1989

  14. [14]

    SoCG , pages=

    Improved approximation algorithms for geometric set cover , author=. SoCG , pages=. 2005 , doi =

    2005

  15. [15]

    ACM Transactions on Algorithms (TALG) , volume=

    On the set multicover problem in geometric settings , author=. ACM Transactions on Algorithms (TALG) , volume=. 2012 , publisher=

    2012

  16. [16]

    Weighted geometric set cover via quasi-uniform sampling , author=. Proc. ACM Symposium on Theory of Computing (STOC) , pages=. 2010 , doi =

    2010

  17. [17]

    Chan and Elyot Grant and Jochen K

    Timothy M. Chan and Elyot Grant and Jochen K. Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling , booktitle =. 2012 , _url =

    2012

  18. [18]

    Varadarajan , title =

    Kasturi R. Varadarajan , title =. Proceedings of the 42nd. 2010 , url =

    2010

  19. [19]

    42nd International Symposium on Computational Geometry (SoCG) , _series =

    Sujoy Bhore and Anupam Gupta and Amit Kumar , title =. 42nd International Symposium on Computational Geometry (SoCG) , _series =. 2026 , _url =

    2026

  20. [20]

    Single-Criteria Metric

    Reilly Browne and Hsien. Single-Criteria Metric. 42nd International Symposium on Computational Geometry (SoCG) , _series =. 2026 , doi =

    2026

  21. [21]

    SIAM Journal on Computing , volume=

    The geometry of scheduling , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    2014

  22. [22]

    Clarkson and Kasturi R

    Kenneth L. Clarkson and Kasturi R. Varadarajan , title =. Discret. Comput. Geom. , volume =. 2007 , doi =

    2007

  23. [23]

    Almost optimal set covers in finite

    Br. Almost optimal set covers in finite. SoCG , pages=. 1994 , doi =

    1994

  24. [24]

    Chan , title =

    Sujoy Bhore and Timothy M. Chan , title =. Proc. 36th Annual. 2025 , doi =

    2025

  25. [25]

    and Maass, Wolfgang , journal=

    Hochbaum, Dorit S. and Maass, Wolfgang , journal=. Approximation schemes for covering and packing problems in image processing and. 1985 , publisher=

    1985

  26. [26]

    SIAM Journal on Computing , volume=

    Polynomial-time approximation schemes for geometric intersection graphs , author=. SIAM Journal on Computing , volume=. 2005 , publisher=

    2005

  27. [27]

    Chan , title =

    Timothy M. Chan , title =. J. Algorithms , volume =. 2003 , doi =

    2003

  28. [28]

    Chan and Sariel Har

    Timothy M. Chan and Sariel Har. Approximation Algorithms for Maximum Independent Set of Pseudo-Disks , journal =. 2012 , doi =

    2012

  29. [29]

    Parinya Chalermsook and Julia Chuzhoy , title =. Proc. 20th Annual. 2009 , doi =

    2009

  30. [30]

    Approximation Schemes for Independent Set and Sparse Subsets of Polygons , journal =

    Anna Adamaszek and Sariel Har. Approximation Schemes for Independent Set and Sparse Subsets of Polygons , journal =. 2019 , _url =

    2019

  31. [31]

    Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =

    Julia Chuzhoy and Alina Ene , title =. Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages =. 2016 , doi =

    2016

  32. [32]

    Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=

    Approximating maximum independent set for rectangles in the plane , author=. Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages=. 2022 , doi =

    2022

  33. [33]

    Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    A 3-approximation algorithm for maximum independent set of rectangles , author=. Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , doi =

    2022

  34. [34]

    Uriel Feige , title =. J. 1998 , url =. doi:10.1145/285055.285059 , timestamp =

    arXiv 1998

  35. [35]

    Approximation Hardness for Small Occurrence Instances of

    Miroslav Chleb. Approximation Hardness for Small Occurrence Instances of. Algorithms and Complexity, 5th Italian Conference (CIAC) , series =. 2003 , _url =. doi:10.1007/3-540-44849-7\_21 , timestamp =

    work page doi:10.1007/3-540-44849-7 2003

  36. [36]

    Approximation hardness of optimization problems in intersection graphs of

    Miroslav Chleb. Approximation hardness of optimization problems in intersection graphs of. Proc. 16th Annual. 2005 , url =

    2005

  37. [37]

    Richard Cole and Kirstin Ost and Stefan Schirra , title =. Comb. , volume =. 2001 , _url =. doi:10.1007/S004930170002 , timestamp =

    doi:10.1007/s004930170002 2001

  38. [38]

    Computing small partial coverings , journal =

    Markus Bl. Computing small partial coverings , journal =. 2003 , url =. doi:10.1016/S0020-0190(02)00434-9 , timestamp =

    work page doi:10.1016/s0020-0190(02)00434-9 2003

  39. [39]

    Chan and Elyot Grant , title =

    Timothy M. Chan and Elyot Grant , title =. Comput. Geom. , volume =. 2014 , _url =. doi:10.1016/J.COMGEO.2012.04.001 , timestamp =

    doi:10.1016/j.comgeo.2012.04.001 2014

  40. [40]

    Chan and Thomas C

    Timothy M. Chan and Thomas C. van Dijk and Krzysztof Fleszar and Joachim Spoerhase and Alexander Wolff , _editor =. Stabbing Rectangles by Line Segments --- How Decomposition Reduces the Shallow-Cell Complexity , booktitle =. 2018 , _url =. doi:10.4230/LIPICS.ISAAC.2018.61 , timestamp =

    work page doi:10.4230/lipics.isaac.2018.61 2018

  41. [41]

    Chan , _editor =

    Timothy M. Chan , _editor =. Approximation Schemes for 0-1 Knapsack , booktitle =. 2018 , _url =. doi:10.4230/OASICS.SOSA.2018.5 , timestamp =

    doi:10.4230/oasics.sosa.2018.5 2018

  42. [42]

    Agarwal and Janos Pach and Micha Sharir , title =

    Pankaj K. Agarwal and Janos Pach and Micha Sharir , title =. Computational Geometry: Twenty Years Later , editor =. 2005 , pages =

    2005

  43. [43]

    Boris Aronov and Anirudh Donakonda and Esther Ezra and Rom Pinchasi , title =. Comput. Geom. , volume =. 2021 , _url =. doi:10.1016/J.COMGEO.2020.101687 , timestamp =

    arXiv 2021

  44. [44]

    Fat Triangles Determine Linearly Many Holes , journal =

    Jir. Fat Triangles Determine Linearly Many Holes , journal =. 1994 , _url =. doi:10.1137/S009753979018330X , timestamp =

    work page doi:10.1137/s009753979018330x 1994

  45. [45]

    Product Range Spaces, Sensitive Sampling, and Derandomization , journal =

    Herv. Product Range Spaces, Sensitive Sampling, and Derandomization , journal =. 1999 , _url =. doi:10.1137/S0097539796260321 , timestamp =

    work page doi:10.1137/s0097539796260321 1999

  46. [46]

    2011 , url =

    Sariel Har-Peled , title =. 2011 , url =

    2011

  47. [47]

    Vazirani , title =

    Vijay V. Vazirani , title =. 2001 , url =

    2001

  48. [48]

    1995 , _url =

    Rajeev Motwani and Prabhakar Raghavan , title =. 1995 , _url =. doi:10.1017/CBO9780511814075 , isbn =

    doi:10.1017/cbo9780511814075 1995

  49. [49]

    Randomized Rounding for Routing and Covering Problems: Experiments and Improvements , booktitle =

    Benjamin Doerr and Marvin K. Randomized Rounding for Routing and Covering Problems: Experiments and Improvements , booktitle =. 2010 , _url =. doi:10.1007/978-3-642-13193-6\_17 , timestamp =

    work page doi:10.1007/978-3-642-13193-6 2010

  50. [50]

    Samir Khuller and Anna Moss and Joseph Naor , title =. Inf. Process. Lett. , volume =. 1999 , _url =. doi:10.1016/S0020-0190(99)00031-9 , timestamp =

    doi:10.1016/s0020-0190(99)00031-9 1999

  51. [51]

    Hochbaum , title =

    Dorit S. Hochbaum , title =. Approximation Algorithms for NP-Hard Problems , publisher =

  52. [52]

    Mustafa and Rajiv Raman and Saurabh Ray , title =

    Nabil H. Mustafa and Rajiv Raman and Saurabh Ray , title =. 2015 , _url =. doi:10.1137/14099317X , timestamp =

    work page doi:10.1137/14099317x 2015

  53. [53]

    Mustafa and Saurabh Ray , title =

    Nabil H. Mustafa and Saurabh Ray , title =. Discret. Comput. Geom. , volume =. 2010 , _url =. doi:10.1007/S00454-010-9285-9 , timestamp =

    doi:10.1007/s00454-010-9285-9 2010

  54. [54]

    Approximation Schemes for Geometric Coverage Problems , booktitle =

    Steven Chaplick and Minati De and Alexander Ravsky and Joachim Spoerhase , _editor =. Approximation Schemes for Geometric Coverage Problems , booktitle =. 2018 , _url =. doi:10.4230/LIPICS.ESA.2018.17 , timestamp =

    work page doi:10.4230/lipics.esa.2018.17 2018

  55. [55]

    Minati De and Abhiruk Lahiri , title =. Comput. Geom. , volume =. 2023 , _url =. doi:10.1016/J.COMGEO.2023.102007 , timestamp =

    arXiv 2023

  56. [56]

    Approximating geometric coverage problems , booktitle =

    Thomas Erlebach and Erik Jan van Leeuwen , _editor =. Approximating geometric coverage problems , booktitle =. 2008 , url =

    2008

  57. [57]

    Ageev and Maxim Sviridenko , title =

    Alexander A. Ageev and Maxim Sviridenko , title =. J. Comb. Optim. , volume =. 2004 , _url =. doi:10.1023/B:JOCO.0000038913.96607.C2 , timestamp =

    arXiv 2004

  58. [58]

    42nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =

    Aravind Srinivasan , title =. 42nd Annual Symposium on Foundations of Computer Science (FOCS) , pages =. 2001 , _url =. doi:10.1109/SFCS.2001.959935 , timestamp =

    arXiv 2001

  59. [59]

    Geometric Packing under Nonuniform Constraints , journal =

    Alina Ene and Sariel Har. Geometric Packing under Nonuniform Constraints , journal =. 2017 , _url =. doi:10.1137/120898413 , timestamp =

    work page doi:10.1137/120898413 2017

  60. [60]

    Stein , title =

    Elias M. Stein , title =. 1993 , url =

    1993

  61. [61]

    Rajiv Raman and Saurabh Ray , title =. Discret. Comput. Geom. , volume =. 2020 , url =. doi:10.1007/S00454-020-00216-W , timestamp =

    work page doi:10.1007/s00454-020-00216-w 2020

  62. [62]

    Varadarajan , _editor =

    Tanmay Inamdar and Kasturi R. Varadarajan , _editor =. On Partial Covering For Geometric Set Systems , booktitle =. 2018 , _url =. doi:10.4230/LIPICS.SOCG.2018.47 , timestamp =

    work page doi:10.4230/lipics.socg.2018.47 2018

  63. [63]

    Varadarajan and Zhao Zhang , title =

    Chandra Chekuri and Tanmay Inamdar and Kent Quanrud and Kasturi R. Varadarajan and Zhao Zhang , title =. J. Comb. Optim. , volume =. 2022 , _url =. doi:10.1007/S10878-022-00874-X , timestamp =

    doi:10.1007/s10878-022-00874-x 2022

  64. [64]

    Covering Many or Few Points with Unit Disks , journal =

    Mark de Berg and Sergio Cabello and Sariel Har. Covering Many or Few Points with Unit Disks , journal =. 2009 , _url =. doi:10.1007/S00224-008-9135-9 , timestamp =

    work page doi:10.1007/s00224-008-9135-9 2009

  65. [65]

    Kai Jin and Jian Li and Haitao Wang and Bowei Zhang and Ningye Zhang , title =. Theor. Comput. Sci. , volume =. 2018 , _url =. doi:10.1016/J.TCS.2017.11.026 , timestamp =

    work page doi:10.1016/j.tcs.2017.11.026 2018

  66. [66]

    Rajiv Raman and Saurabh Ray , title =. Discret. Comput. Geom. , volume =. 2022 , url =

    2022

  67. [67]

    Topological hypergraphs , booktitle =

    Sarit Buzaglo and Rom Pinchasi and G. Topological hypergraphs , booktitle =. 2012 , doi =

    2012

  68. [68]

    2026 , doi =

    Pallavi Jain and Lawqueen Kanesh and Fahad Panolan and Souvik Saha and Abhishek Sahu and Saket Saurabh and Anannya Upasana , title =. 2026 , doi =

    2026

  69. [69]

    2010 , _url =

    Boris Aronov and Esther Ezra and Micha Sharir , title =. 2010 , _url =. doi:10.1137/090762968 , timestamp =

    work page doi:10.1137/090762968 2010

  70. [70]

    SODA , pages =

    Pasin Manurangsi , title =. SODA , pages =. 2020 , url =. doi:10.1137/1.9781611975994.5 , timestamp =

    work page doi:10.1137/1.9781611975994.5 2020

  71. [71]

    Vincent Cohen. Tight. ICALP , pages =. 2019 , url =. doi:10.4230/LIPICS.ICALP.2019.42 , timestamp =

    doi:10.4230/lipics.icalp.2019.42 2019

  72. [72]

    ICALP , pages =

    Pasin Manurangsi and Prasad Raghavendra , title =. ICALP , pages =. 2017 , url =. doi:10.4230/LIPICS.ICALP.2017.78 , timestamp =

    doi:10.4230/lipics.icalp.2017.78 2017

  73. [73]

    Electron

    Irit Dinur , title =. Electron. Colloquium Comput. Complex. , volume =. 2016 , url =. TR16-128 , timestamp =

    2016

  74. [74]

    2026 , month =

    Saket Saurabh , title =. 2026 , month =

    2026