A PTAS for the Weighted Unit Disk Cover Problem
From MaRDI portal
Publication:3448847
DOI10.1007/978-3-662-47672-7_73zbMath1440.68335arXiv1502.04918OpenAlexW1655323853MaRDI QIDQ3448847
Publication date: 27 October 2015
Published in: Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.04918
Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items (19)
Theoretical complexity of grid cover problems used in radar applications ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ On the geometric set multicover problem ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Exact algorithms and hardness results for geometric red-blue hitting set problem ⋮ Geometric dominating-set and set-cover via local-search ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions. ⋮ On the geometric red-blue set cover problem ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Near-linear time approximation schemes for geometric maximum coverage ⋮ The within-strip discrete unit disk cover problem ⋮ Algorithms for the line-constrained disk coverage and related problems ⋮ Computing a tree having a small vertex cover ⋮ Approximation algorithms for the connected sensor cover problem ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks ⋮ A constant-factor approximation algorithm for red-blue set cover with unit disks ⋮ Constant-approximation for minimum weight partial sensor cover
Cites Work
- Unnamed Item
- Tighter estimates for \(\epsilon\)-nets for disks
- Exact algorithms and APX-hardness results for geometric packing and covering problems
- New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
- Improved approximation algorithms for geometric set cover
- A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph
- A better constant-factor approximation for weighted dominating set in unit disk graph
- Hitting sets when the VC-dimension is small
- Unit disk graphs
- Almost optimal set covers in finite VC-dimension
- Weighted geometric set cover via quasi-uniform sampling
- WEIGHTED GEOMETRIC SET COVER PROBLEMS REVISITED
- A threshold of ln n for approximating set cover
- A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- PTAS for Weighted Set Cover on Unit Squares
- Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
- New existence proofs ε-nets
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast approximation algorithms for a nonconvex covering problem
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- The Geometry of Scheduling
- Analytical approach to parallel repetition
- Epsilon nets and union complexity
- PTAS for geometric hitting set problems via local search
This page was built for publication: A PTAS for the Weighted Unit Disk Cover Problem
