Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces

DOI10.1137/14099317XzbMath1333.68259MaRDI QIDQ3451756

Nabil H. Mustafa, Rajiv Raman, Saurabh Ray

Publication date: 18 November 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsset coverpolynomial time approximation schemespseudodisks

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items

Mallows-Smoothed Distribution over Rankings Approach for Modeling Choice, Tighter estimates for \(\epsilon\)-nets for disks, A PTAS for the horizontal rectangle stabbing problem, Minimum power partial multi-cover on a line, On the geometric priority set cover problem, Geometric dominating-set and set-cover via local-search, A game theoretic approach for minimal connected dominating set, Geometric stabbing via threshold rounding and factor revealing LPs, Constrained hitting set problem with intervals: hardness, FPT and approximation algorithms, Unnamed Item, Constrained hitting set problem with intervals, Constructing planar support for non-piercing regions, Planar Support for Non-piercing Regions and Applications, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, Packing and covering with non-piercing regions, Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs, Unnamed Item, On Geometric Set Cover for Orthants, Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks, A primal-dual algorithm for the minimum power partial cover problem

Cites Work

• Approximating hitting sets of axis-parallel rectangles intersecting a monotone curve
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Improved results on geometric hitting set problems
• Improved approximation algorithms for geometric set cover
• Finding small simple cycle separators for 2-connected planar graphs
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Weighted geometric set cover via quasi-uniform sampling
• WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
• Learnability and the Vapnik-Chervonenkis dimension
• Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Non-approximability results for optimization problems on bounded degree instances
• A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item