Source-linked AI summary
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks
Timothy M. Chan, Sariel Har-Peled
TL;DR
The paper studies maximum independent set for intersecting planar objects, where general intersection-graph hardness and the failure of simple packing arguments make approximation challenging. It develops local search for unweighted pseudo-disks and LP-based randomized rounding for weighted instances, obtaining a PTAS in the unweighted case and a constant-factor approximation in the weighted case.
Problem
Maximum independent set is NP-complete, has strong general hardness, and simple packing-based greedy methods do not extend naturally to pseudo-disks.
Method
The paper combines local search with combinatorial geometric techniques, using local search for unweighted pseudo-disks and LP relaxation followed by resistance-ordered randomized rounding for weighted instances.
Results
The unweighted algorithm yields a PTAS for pseudo-disks, while the weighted rounding approach yields a constant-factor approximation.
Takeaways & Limitations
The results extend local-search analysis to arbitrary pseudo-disks and provide an LP-based approximation approach where standard packing arguments are unavailable.
Takeaways & Limitations
The paper's highlighted strategy applies only in the unweighted case, while the admissible-region analysis assumes pairwise set differences are simply connected and regions are not nested.
Abstract
from arXiv · showhide
We present approximation algorithms for maximum independent set of pseudo-disks in the plane, both in the weighted and unweighted cases. For the unweighted case, we prove that a local search algorithm yields a \PTAS. For the weighted case, we suggest a novel rounding scheme based on an \LP relaxation of the problem, which leads to a constant-factor approximation. Most previous algorithms for maximum independent set (in geometric settings) relied on packing arguments that are not applicable in this case. As such, the analysis of both algorithms requires some new combinatorial ideas, which we believe to be of independent interest.
1 Introduction
The paper studies maximum independent set for weighted and unweighted pseudo-disks, where prior geometric techniques do not directly apply. It develops a local-search PTAS for the unweighted case and an LP-based constant-factor approximation for the weighted case, with extensions to related object classes.
- Problem: Maximum independent set asks for a largest-weight subset of pairwise nonintersecting planar objects.The paper considers both weighted and unweighted pseudo-disks.
- Motivation: Previous geometric approaches for fat objects use packing, spatial subdivision, or separator techniques, but these methods do not directly extend to pseudo-disks.Pseudo-disks are defined topologically by pairwise boundary intersections occurring at most twice.
- Unweighted case: A local-search algorithm yields a PTAS for unweighted pseudo-disks.The algorithm requires only the intersection graph as input; the planar separator theorem is used only in the analysis.
- Weighted case: The weighted algorithm solves an independent-set LP, then rounds its fractional solution using a resistance-based greedy ordering.The rounding analysis bounds intersecting-pair terms x_i x_j through the union boundary complexity and guarantees selection probability Ω(x_i).
- Extensions: The same local-search approach yields a PTAS for fat objects in any fixed dimension and a constant-factor approximation for unweighted objects with linear union complexity.For planar graphs, the result also shows that simple local search yields a PTAS.
- Extensions: The LP-based approach also gives a sublogarithmic O(log n/ log log n) approximation for weighted axis-parallel rectangles.The result improves on the previously known logarithmic approximation, while a stronger result applies only to unweighted rectangles.
- Methodological contribution: The paper’s main methodological contribution is combining local search and LP relaxation with combinatorial geometric techniques.The rounding scheme is also described as applicable to maximizing submodular target functions.
- Combinatorial consequence: For pseudo-disks, the minimum piercing-set size is at most a constant factor larger than the maximum independent-set size.The stated theorem gives opt = Ω(opt′), where opt is the maximum independent-set size and opt′ is the minimum piercing-set size.
2 Preliminaries
The preliminaries assume linear union complexity for object subsets and constant-time intersection testing.
- Union complexity: Any subset X of the object family has union complexity at most a constant times |X|.Union complexity is the number of arcs on the boundary of the union.
- Computational assumption: The analysis assumes that deciding whether two objects intersect takes constant time.
3 Approximation by Local Search: Unweighted Case
The unweighted algorithm seeks a b-locally optimal independent set through local exchanges. Under linear union complexity, admissibility, or fatness assumptions, the resulting solution approximates the optimum, including PTAS guarantees.
- 3.1 The algorithm: A b-locally optimal solution cannot be improved by deleting at most b objects and inserting at most b + 1 objects.The algorithm tests independent candidate sets X and replaces intersecting objects Y whenever |Y| ≤ |X| − 1.
- 3.2.1 Analysis using union complexity: For sufficiently large constant b, every b-locally optimal independent set among objects with linear union complexity has size Ω(opt).The analysis uses a lemma bounding equivalent curve classes and separates optimal objects according to how many local-search objects they intersect.
- 3.2.2 Better analysis for admissible regions: For admissible regions, setting b to the order of 1/ε^2 computes an independent set of size at least (1 − ε)opt in time n^O(1/ε^2).Thus, the local-search method gives a PTAS in this setting.
- 3.2.2 Better analysis for admissible regions: Under the admissible-region condition, a b-locally optimal independent set has size at least (1 − O(1/b))opt.The analysis uses planarity of the intersection graph formed by two independent sets and a planar separator decomposition.
- Fat objects: For fat objects in fixed dimension d, any b-locally optimal independent set has size at least (1 − O(1/b^1/d))opt.The corresponding PTAS runs in time n^O(1/ε^d), using a fat-object separator theorem.
4 Approximation by LP Relaxation: Weighted Case
The weighted algorithm rounds an LP relaxation using a resistance-based ordering and randomized selection. Its analysis yields an Ω(n/u(n))-approximation, giving a constant-factor algorithm for weighted pseudo-disks and a constant piercing-set relation in the unweighted case.
- LP relaxation: The method solves a packing LP with one variable per object and uses its fractional values to guide rounding.The relaxed optimum is at least the optimal integral weight.
- Resistance ordering: Objects are ordered by increasing resistance, defined as the total fractional value of objects intersecting each object.The algorithm extracts a minimum-resistance object at each step and scans the resulting permutation in reverse.
- Analysis: The Clarkson-style analysis bounds resistance through union complexity, enabling the randomized rounding scheme to retain independent-set weight.The analysis uses random sampling, union-complexity bounds, and concentration inequalities.
- Guarantee: Ω((n/u(n))opt) weight is obtained for weighted objects with union complexity O(u(n)), in O(n3) randomized time and polynomial deterministic time.The randomized algorithm can be derandomized by conditional expectations.
- Consequences: Constant-factor approximation follows for maximum-weight independent set of pseudo-disks, while the same analysis supports an O(1)-approximation for discrete independent set.The framework also extends to submodular objectives and yields a constant relation between piercing number and maximum independent-set size in the unweighted case.
5 Weighted Rectangles
For weighted axis-aligned rectangles, the algorithm first handles a subgraph with the LP method and then uses coloring to control the remaining intersections. This yields an Ω(log log n/log n) approximation in polynomial time.
- Graph decomposition: Rectangle pairs are partitioned into G1, whose boundaries intersect zero or two times, and G2, whose boundaries intersect four times.The two subgraphs are analyzed separately.
- First stage: An independent set I of G1 is extracted using the LP-based algorithm, and its expected total weight is Ω(Opt).The argument uses the fact that each G1 intersection contains a corner of one rectangle in the other.
- Depth control: The maximum depth of a random rectangle arrangement is O(log n/log log n) with probability at least 1−1/n.A Chernoff bound and a union bound over arrangement vertices establish this depth control.
- Final guarantee: Ω(log log n/log n)·opt weight is computable in polynomial time for weighted axis-aligned boxes in the plane.Conditional expectations derandomize the procedure by using a lower-bounding random variable whose expectation is computable exactly.
- Higher dimensions: In fixed dimension d, a divide-and-conquer extension gives an O(log^(d−1)n/log log n) approximation for weighted axis-aligned boxes.The higher-dimensional statement is obtained by a standard divide-and-conquer method.