A PTAS for the Weighted Unit Disk Cover Problem

DOI10.1007/978-3-662-47672-7_73MaRDI QIDQ3448847zbMATH OpenOpenAlexFDO

Authors Jian Li, Yifei Jin

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: We are given a set of weighted unit disks and a set of points in Euclidean plane. The minimum weight unit disk cover (UDC) problem asks for a subset of disks of minimum total weight that covers all given points. UDC is one of the geometric set cover problems, which have been studied extensively for the past two decades (for many different geometric range spaces, such as (unit) disks, halfspaces, rectangles, triangles). It is known that the unweighted UDC problem is NP-hard and admits a polynomial-time approximation scheme (PTAS). For the weighted UDC problem, several constant approximations have been developed. However, whether the problem admits a PTAS has been an open question. In this paper, we answer this question affirmatively by presenting the first PTAS for UDC. Our result implies the first PTAS for the minimum weight dominating set problem in unit disk graphs. Combining with existing ideas, our result can also be used to obtain the first PTAS for the maxmimum lifetime coverage problem and an improved constant approximation ratio for the connected dominating set problem in unit disk graphs.

Recommendations

• Computing and Combinatorics
• A PTAS for a disc covering problem using width-bounded separators
• A PTAS for the disk cover problem of geometric objects
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs
• PTAS for connected vertex cover in unit disk graphs
• PTAS for the minimum \(k\)-path connected vertex cover problem in unit disk graphs
• On the discrete unit disk cover problem
• On the discrete unit disk cover problem
• PTAS for weighted set cover on unit squares

Cites work

• A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs
• 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
• A threshold of ln n for approximating set cover
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Almost optimal set covers in finite VC-dimension
• Analytical approach to parallel repetition
• Approximation schemes for covering and packing problems in image processing and VLSI
• Constant-Factor Approximation for Minimum-Weight (Connected) Dominating Sets in Unit Disk Graphs
• Epsilon nets and union complexity
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Fast approximation algorithms for a nonconvex covering problem
• Hitting sets when the VC-dimension is small
• Improved approximation algorithms for geometric set cover
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• New existence proofs ε-nets
• PTAS for geometric hitting set problems via local search
• PTAS for weighted set cover on unit squares
• The geometry of scheduling
• Tighter estimates for -nets for disks
• Unit disk graphs
• Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling
• Weighted geometric set cover problems revisited
• Weighted geometric set cover via quasi-uniform sampling

Cited in

(31)

• Algorithms for the line-constrained disk coverage and related problems
• Algorithms for the line-constrained disk coverage and related problems
• On line-separable weighted unit-disk coverage and related problems
• On the geometric red-blue set cover problem
• PTAS for connected vertex cover in unit disk graphs
• Exact algorithms and hardness results for geometric red-blue hitting set problem
• Theoretical complexity of grid cover problems used in radar applications
• A PTAS for the minimum weight connected vertex cover \(P_3\) problem on unit disk graphs
• Near-linear time approximation schemes for geometric maximum coverage
• PTAS for weighted set cover on unit squares
• Improved Approximation Algorithm for Set Multicover with Non-Piercing Regions.
• Constant-approximation for minimum weight partial sensor cover
• PTAS for minimum cost multicovering with disks
• On the line-separable unit-disk coverage and related problems
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• On the geometric red-blue set cover problem
• On line-separable weighted unit-disk coverage and related problems
• Parallel algorithm for minimum partial dominating set in unit disk graph
• Unweighted geometric hitting set for line-constrained disks and related problems
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• On the geometric set multicover problem
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• Geometric dominating-set and set-cover via local-search
• Set cover, hitting set, and independent set problems for some restricted classes of geometric objects
• Algorithms for halfplane coverage and related problems
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• A constant-factor approximation algorithm for red-blue set cover with unit disks
• Geometric covering via extraction theorem
• On the line-separable unit-disk coverage and related problems
• A PTAS for the cardinality constrained covering with unit balls
• The within-strip discrete unit disk cover problem

This page was built for publication: A PTAS for the Weighted Unit Disk Cover Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3448847)