Approximation algorithms for maximum independent set of pseudo-disks

DOI10.1007/s00454-012-9417-5zbMath1248.05135OpenAlexW2077735330WikidataQ56335605 ScholiaQ56335605MaRDI QIDQ452004

Publication date: 19 September 2012

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9417-5

zbMATH Keywords

approximation algorithms PTAS polynomial-time approximation scheme Fréchet distance realistic input models

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial aspects of finite geometries (05B25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (69)

Packing and covering with balls on Busemann surfaces ⋮ Minimum Point-Overlap Labeling ⋮ Stochastic Makespan Minimization in Structured Set Systems (Extended Abstract) ⋮ Generalized disk graphs ⋮ A $$(2+\epsilon )$$-Approximation Algorithm for the Storage Allocation Problem ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ Submodular Unsplittable Flow on Trees ⋮ Improved bounds on the Hadwiger-Debrunner numbers ⋮ Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs ⋮ On the geometric set multicover problem ⋮ APPROXIMATION ALGORITHMS FOR A VARIANT OF DISCRETE PIERCING SET PROBLEM FOR UNIT DISKS ⋮ On independent set in $B_1$-EPG graphs ⋮ Existence of planar support for geometric hypergraphs using elementary techniques ⋮ Efficient independent set approximation in unit disk graphs ⋮ Space-efficient algorithms for reachability in directed geometric graphs ⋮ A tight $(3/2+\varepsilon)$-approximation for skewed strip packing ⋮ From a $(p, 2)$-theorem to a tight $(p, q)$-theorem ⋮ Geometric Packing under Nonuniform Constraints ⋮ On the geometric priority set cover problem ⋮ Geometric dominating-set and set-cover via local-search ⋮ Geometric stabbing via threshold rounding and factor revealing LPs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On streaming algorithms for geometric independent set and clique ⋮ Winner determination in geometrical combinatorial auctions ⋮ Lower bounds for piercing and coloring boxes ⋮ Unnamed Item ⋮ Conflict-free coloring of intersection graphs of geometric objects ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ Constructing planar support for non-piercing regions ⋮ Practical and efficient algorithms for the geometric hitting set problem ⋮ Shifting strategy for geometric graphs without geometry ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Computing inductive vertex orderings ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Independent set of convex polygons: from $n^{\epsilon}$ to $1+\epsilon $ via shrinking ⋮ A note on fractional coloring and the integrality gap of LP for maximum weight independent set ⋮ Matching colored points with rectangles ⋮ Packing and covering with non-piercing regions ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ A Tight (3/2+ε) Approximation for Skewed Strip Packing. ⋮ Anchored rectangle and square packings ⋮ Piercing axis-parallel boxes ⋮ Minimum vertex cover in ball graphs through local search ⋮ On Wegner's inequality for axis-parallel rectangles ⋮ From a $(p,2)$-Theorem to a Tight $(p,q)$-Theorem ⋮ Improved Algorithm for Maximum Independent Set on Unit Disk Graph ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains ⋮ Submodular unsplittable flow on trees ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Unnamed Item ⋮ Maximum independent and disjoint coverage ⋮ Covering and packing of rectilinear subdivision ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Local search strikes again: PTAS for variants of geometric covering and packing ⋮ Approximability of covering cells with line segments ⋮ Limit theory of combinatorial optimization for random geometric graphs ⋮ Approximation and Parameterized Algorithms for Geometric Independent Set with Shrinking ⋮ Minimum point-overlap labelling* ⋮ Approximating dominating set on intersection graphs of rectangles and $\mathsf{L}$-frames ⋮ Independent and hitting sets of rectangles intersecting a diagonal line: algorithms and complexity ⋮ Topological Drawings Meet Classical Theorems from Convex Geometry ⋮ Simple PTAS's for families of graphs excluding a minor ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ A tight analysis of geometric local search ⋮ Stochastic makespan minimization in structured set systems

Cites Work

This page was built for publication: Approximation algorithms for maximum independent set of pseudo-disks