Local search strikes again: PTAS for variants of geometric covering and packing

DOI10.1007/s10878-019-00432-yzbMath1434.68597OpenAlexW2950798640MaRDI QIDQ5919362

Sathish Govindarajan, Pradeesha Ashok, Aniket Basu Roy

Publication date: 3 February 2020

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-019-00432-y

zbMATH Keywords

coveringlocal searchpackingPTASnon-piercing regions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (1)

Exact multi-covering problems with geometric sets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the efficiency of polynomial time approximation schemes
• Approximation algorithms for maximum independent set of pseudo-disks
• Algorithms for four variants of the exact satisfiability problem
• Improved results on geometric hitting set problems
• Optimal packing and covering in the plane are NP-complete
• A 4.31-approximation for the geometric unique coverage problem on unit disks
• The parameterized complexity of unique coverage and its variants
• Effectiveness of local search for art gallery problems
• Geometric packing under non-uniform constraints
• A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares
• On the set multicover problem in geometric settings
• Guarding terrains via local search
• Weighted geometric set multi-cover via quasi-uniform sampling
• Unique Covering Problems with Geometric Sets
• Combination Can Be Hard: Approximability of the Unique Coverage Problem
• New existence proofs ε-nets
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Packing and Covering with Non-Piercing Regions
• Local Search Yields a PTAS for $k$-Means in Doubling Metrics
• Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics
• Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
• Approximation Schemes for Covering and Packing
• Decomposition of Multiple Packings with Subquadratic Union Complexity
• The complexity of satisfiability problems

This page was built for publication: Local search strikes again: PTAS for variants of geometric covering and packing