A primal-dual algorithm for the minimum power partial cover problem
From MaRDI portal
Publication:2082206
DOI10.1007/s10878-020-00567-3zbMath1502.90152OpenAlexW3015834807MaRDI QIDQ2082206
Menghong Li, Yingli Ran, Zhao Zhang
Publication date: 4 October 2022
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-020-00567-3
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
A note on the minimum power partial cover problem on the plane ⋮ The bound coverage problem by aligned disks in \(L_1\) metric ⋮ An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
Cites Work
- Unnamed Item
- Unnamed Item
- Improved performance of the greedy algorithm for partial cover
- Approximation algorithm for partial positive influence problem in social network
- Improved results on geometric hitting set problems
- Approximation algorithms for combinatorial problems
- A note on multicovering with disks
- Packing and covering with non-piercing regions
- A primal-dual algorithm for the minimum partial set multi-cover problem
- Local ratio method on partial set multi-cover
- Fault-tolerant covering problems in metric spaces
- Using Homogeneous Weights for Approximating the Partial Cover Problem
- Weighted geometric set cover via quasi-uniform sampling
- Weighted Geometric Set Multi-cover via Quasi-uniform Sampling
- A constant-factor approximation for multi-covering with disks
- Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces
- A Greedy Heuristic for the Set-Covering Problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Approximation algorithm for partial set multicover versus full set multicover
- Approximation algorithms for partial covering problems
- On Partial Covering For Geometric Set Systems
