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 (20)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces