Source-linked AI summary
Geometric Optimization Parameterized by Piercing Complexity
Aritra Banik, Rajiv Raman, Saurabh Ray
TL;DR
Familiar geometric complexity restrictions often yield constant-factor approximations but do not generally yield PTASs, while hardness constructions feature many piercing pairs. The paper uses local search with adaptive balanced separators for unweighted problems and polynomial shallow-trace bounds for weighted guarantees. For piercing degree at most r, t-local search yields (1+ϵ)- and (1−ϵ)-approximations for Set Cover and Discrete Independent Set, respectively; fixed r also gives deterministic C_r and O(r+1) weighted approximations.
Problem
Familiar geometric complexity restrictions often yield constant-factor approximations but do not generally yield PTASs, while hardness constructions feature many piercing pairs.
Source: §1 · pp. 1–2Method
The paper uses local search with adaptive balanced separators for unweighted problems and polynomial shallow-trace bounds for weighted guarantees.
Source: §1 · pp. 2–3Results
For piercing degree at most r, t-local search yields (1+ϵ)- and (1−ϵ)-approximations for Set Cover and Discrete Independent Set, respectively; fixed r also gives deterministic C_r and O(r+1) weighted approximations.
Source: §1 · pp. 2–3Takeaways & Limitations
The algorithms run in polynomial time for constant r and give QPTASs when r is polylogarithmic in n.
Source: §1 · p. 2Comparable guarantees for Hitting Set remain open, as does how far bounded piercing can be relaxed for axis-parallel rectangles and other classical families.
Source: §8 · p. 15
Abstract
from arXiv · showhide
Packing and covering problems for geometric regions have been studied under many notions of complexity, including VC-dimension, union complexity, shallow-cell complexity, and fatness. Although these restrictions often yield constant-factor approximation algorithms, they do not by themselves generally lead to PTASs. A recurring feature of known hardness constructions is that one region may be \emph{pierced} by many others: a region $B$ pierces $A$ when $A\setminus B$ is disconnected. We study geometric instances through the \emph{piercing degree}. Since piercing is symmetric for Jordan regions, this is the maximum degree of the corresponding piercing graph. Our main result is that, for every fixed piercing degree, the standard local-search algorithms give PTASs for the unweighted \emph{Discrete Independent Set} and \emph{Set Cover} problems. The proof constructs a sublinear balanced separator for an appropriate locality graph and applies it adaptively throughout the recursive local-search analysis. This guarantee depends only on the piercing degree; in particular, it places no bound on the number of components created by an individual piercing pair. We also prove a polynomial shallow-trace bound depending only on the piercing degree. As consequences, for every fixed piercing degree, weighted Set Cover admits a deterministic $C_r$-approximation and weighted Discrete Independent Set admits a deterministic $O(r+1)$-approximation. These results extend the known guarantees for non-piercing families and apply, for example, to axis-parallel rectangles when every rectangle is pierced by only a bounded number of other rectangles.
1 Introduction
The introduction asks whether bounding piercing can recover strong approximation guarantees where familiar geometric complexity measures do not. It answers yes for fixed piercing degree, using local search for unweighted problems and shallow-trace bounds for weighted guarantees.
1 Introduction
- Small conventional complexity measures do not always yield PTASs: simple geometric families can remain APX-hard, and hardness constructions feature many piercing pairs.Source: §1 · pp. 1–2
- Piercing degree bounds how many other regions pierce each region, without limiting the number of components created by any one piercing pair.Piercing is symmetric for Jordan regions.Source: §1 · p. 2
- For piercing degree at most r, t-local search gives a (1+ϵ)-approximation for Set Cover and a (1−ϵ)-approximation for Discrete Independent Set, with t polynomial in (r+1)/ϵ up to logarithmic factors.The stated running time is |P|n^O(t).Source: §1 · p. 2
- For axis-parallel rectangles, both unweighted problems are APX-hard in general, but the paper gives PTASs when each rectangle is pierced by only a bounded number of others.Source: §1 · p. 2
- For every fixed r, shallow-trace bounds yield a deterministic C_r-approximation for weighted Set Cover, while weighted Discrete Independent Set has a deterministic O(r + 1)-approximation.C_r is constant for each fixed r; no uniform polynomial dependence on r is claimed.Source: §1 · p. 3
- The local-search analysis builds locality graphs, obtains sublinear balanced separators, and recursively recomputes them to control overlap.Bounded piercing permits partitioning into non-piercing families; the separator argument uses odd-crossing bisection and an ϵ-net.Source: §1 · p. 3
- The corrected version replaces a conference proof whose monotonicity lemma and sampling-based shallow-trace argument were invalid.The authors characterize these as proof errors, not counterexamples to the unweighted PTAS statements.Source: §1 · p. 3
1.1 Related Work
- Prior work uses ϵ-nets for covering and local search for unweighted optimization; planar supports for non-piercing families underpin several PTAS results.The introduction also situates these approaches among work on fat-object packing, non-fat regions, and higher-genus surfaces.Source: §1.1 · pp. 3–4
2 Preliminaries
The preliminaries define the geometric objects and piercing parameter, then introduce traces and locality graphs used in the analysis. They also state the separator framework used to support local search.
2 Preliminaries
- A region is a closed Jordan domain bounded by a simple Jordan curve, and no bound is imposed on boundary intersections or components of α \ β.Source: §2 · p. 4
- β pierces α when α \ β is disconnected; for Jordan regions this relation is symmetric, so piercing degree is the maximum degree of the piercing graph.Source: §2 · p. 4
- A trace records the regions containing an input point, while a locality graph connects red and blue regions so every mixed trace contains an edge.A minimum locality graph has the fewest edges among graphs satisfying that condition.Source: §2 · p. 4
- Shallow-cell complexity bounds the number of distinct traces of size at most k across every m-region subfamily; a constant function gives constant shallow-cell complexity.Source: §2 · pp. 4–5
- The separator background defines 2/3-balanced vertex separators and edge bisections, and states that planar drawings admit balanced bisections governed by odd-crossing counts.The odd-crossing quantity is minimized over plane drawings of the graph.Source: §2 · p. 5
3 Main Results
The main results give local-search approximation guarantees for unweighted Set Cover and Discrete Independent Set, plus a shallow-trace bound and deterministic approximations for weighted variants. The algorithms use incidence data, with geometry entering through the analysis.
3 Main Results
- The local-search algorithms use only point-region incidence; the geometric representation is needed for locality-graph and separator analysis.Source: §3 · p. 5
- For every ϵ ∈ (0, 1], t-local search gives a (1−ϵ)-approximation for Discrete Independent Set and a (1+ϵ)-approximation for Set Cover, with t a sufficiently large constant multiple of ((r+1)/ϵ)^4 log^3(2+(r+1)/ϵ).Both algorithms run in time |P|n^O(t).Source: §3 · p. 5
- For every fixed r, the number of traces of size at most k is bounded by a polynomial in m and k, giving constant shallow-cell complexity.The theorem states that the exponent's hidden constant is absolute.Source: §3 · p. 5
- For every fixed r, weighted Set Cover has a deterministic polynomial-time C_r-approximation and weighted Discrete Independent Set has a deterministic polynomial-time O(r + 1)-approximation.C_r depends only on r; the weighted Set Cover guarantee does not claim uniform polynomial dependence on r.Source: §3 · p. 5
4 Locality Separators
For fixed piercing degree, this section constructs locality graphs with sublinear balanced separators and uses them adaptively to obtain locality divisions with small boundaries and bounded-size groups. It also bounds the dual set system’s VC-dimension and gives separator guarantees in terms of essential-trace sizes, with a single graph built from bichromatic pairs at leaf bags and recomputed at each recursive step.
4.1 Sparse locality graphs and bounded VC-dimension
- The dual set system and all its restrictions have VC-dimension at most 4(r + 1), while D(S) and minimum locality graphs have O((r + 1)|S|) edges.The hereditary density bound uses the absolute constant c = 25.Source: §4.1 · p. 6
4.2 A separator from essential traces
- If every essential trace has size at most k, a minimum locality graph on s vertices has a 2/3-balanced separator of size O((r + 1)s^2/3 k^1/3 log^2/3(2 + s)).The proof bounds odd-crossing independent edge pairs by O(∆0(rm + T)), where T is total essential-trace incidence.Source: §4.2 · pp. 7–9
4.3 Locality graph with sublinear separator
- Every finite trace collection on an s-element subfamily of a two-coloured r-piercing family has a locality graph with a 2/3-balanced vertex separator of size O((r + 1)s^3/4 log^3/4(2 + s)).The construction removes a set meeting all traces larger than k, then applies the essential-trace separator to the remaining small traces.Source: §4.3 · p. 9
4.4 Adaptive recursion
- For any δ ∈ (0, 1), the locality division provides X so V \ X partitions into groups of size at most t; every locality-graph edge has both endpoints in some Gi ∪ X, and q = O(1 + |V|/t).Source: §4.4 · p. 11
- The construction follows each mixed trace to a leaf bag where it remains mixed, then selects one bichromatic pair to define the locality graph.If the leaf bag's group remains, the selected edge lies in that group together with the exceptional set; if the group was omitted, both endpoints lie in the exceptional set.Source: §4.4 · p. 11
- Unlike Frederickson’s division for planar graphs, the locality graph and its separator are recomputed at every recursive step rather than reused as one fixed graph.The exceptional-set neighborhood bound is aggregate rather than per group, which the local-search proofs need.Source: §4.4 · p. 11
5 PTAS for Discrete Independent Set and Set Cover
For every fixed piercing degree, t-local search gives PTASs for Discrete Independent Set and Set Cover. The analysis uses feasible local exchanges derived from a locality graph to certify the guarantees.
5 PTAS for Discrete Independent Set and Set Cover
- The algorithm repeatedly replaces at most t solution regions with at most t others whenever the replacement improves the objective, stopping at a t-locally optimal solution.A straightforward implementation runs in time |P|n^O(t).Source: §5 · p. 12
- A sufficiently large constant multiple of ((r + 1)/ϵ)^4 log^3(2 + (r + 1)/ϵ) gives a (1 − ϵ)-approximation for Discrete Independent Set and a (1 + ϵ)-approximation for Set Cover, in time |P|n^O(t).The exchange radius t has this order for both problems.Source: §5 · pp. 12–13
- For Discrete Independent Set, locality-graph exchanges delete conflicting blue regions and insert red regions, so local optimality bounds each inserted group by its deleted neighbors.The exchange is feasible because every conflict with an inserted region is represented by a two-element mixed trace and its locality edge.Source: §5 · p. 12
- For Set Cover, replacing B \ Bi with Ri covers every remaining point, and local optimality gives |Bi| ≤ |Ri| for each group.The proof applies the recursive division to the red and blue regions and uses a different exchange from the Discrete Independent Set proof.Source: §5 · p. 13
6 Shallow traces
The section bounds shallow traces using structural properties of the dual set system and injective signatures. For fixed piercing degree, this yields constant shallow-cell complexity and linear-size ϵ-nets.
6 Shallow traces
- For every fixed r, the dual set system has constant shallow-cell complexity.The theorem gives a shallow-trace bound, with an absolute constant hidden in the exponent.Source: §6 · p. 13
- The dual set system is 25(r + 1)-linear, and injective signatures let sampling count distinct small traces without collisions.The proof uses the Clarkson–Shor sampling argument; distinct surviving traces retain distinct signatures on the sample.Source: §6 · pp. 13–14
- For fixed r, the dual set system has ϵ-nets of size O_r(1/ϵ), improving on the classical VC-theorem bound O((r + 1)ϵ^-1 log(1/ϵ)).The linear-size bound follows from the shallow-cell result and quasi-uniform sampling [9].Source: §6 · p. 14
7 Weighted problems
For fixed piercing degree, the paper gives deterministic approximation algorithms for both weighted problems. It derives the Set Cover guarantee from shallow traces and the Discrete Independent Set guarantee through LP rounding.
7 Weighted problems
- For every fixed r, weighted Set Cover has a deterministic polynomial-time C_r-approximation, while weighted Discrete Independent Set has a deterministic polynomial-time O(r + 1)-approximation.C_r depends only on r; the paper does not claim a uniform polynomial dependence of C_r on r.Source: §7 · pp. 14–15
- For weighted Set Cover, the shallow-trace profile and derandomized quasi-uniform sampling yield the C_r-approximation through the dual hitting-set formulation.The analysis does not claim a uniform polynomial dependence of C_r on r.Source: §7 · p. 15
- For weighted Discrete Independent Set, LP rounding uses a conflict-density bound to find vertices with O(r + 1) neighbor x-mass, then processes them in reverse elimination order.Each region is proposed with probability proportional to its LP value and accepted if no already processed neighbor was proposed.Source: §7 · pp. 14–15
- Conditional-expectation derandomization produces a feasible independent set with at least the expected weight of the randomized rounding.The accepted set has expected weight proportional to (r + 1)^-1 times the LP objective.Source: §7 · p. 15
8 Conclusion
The conclusion collects the guarantees controlled by piercing degree and describes the proof’s analysis tools. It leaves open comparable Hitting Set guarantees and how far bounded piercing can be relaxed for rectangles and other classical families.
8 Conclusion
- Piercing degree alone controls locality structures sufficient for unweighted PTASs, polynomial shallow-trace bounds, and the stated weighted approximation guarantees.For fixed piercing degree, weighted Set Cover has a constant-factor approximation and weighted Discrete Independent Set has an O(r + 1)-approximation.Source: §8 · p. 15
- Minimum locality graphs, parity separators, and adaptive recursive division certify global near-optimality while leaving the algorithm as exhaustive local search.These tools are used in the analysis, not as changes to the local-search algorithm.Source: §8 · p. 15
- Comparable guarantees for Hitting Set and relaxing bounded piercing for axis-parallel rectangles and other classical families remain open questions.Source: §8 · p. 15