An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem

DOI10.3934/jimo.2023140OpenAlexW4388186407MaRDI QIDQ6149344

Wencheng Wang, Tongquan Zhang, Yinhua Chen, Jianglin Li, Binhui Cheng

Publication date: 5 February 2024

Published in: Journal of Industrial and Management Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/jimo.2023140

zbMATH Keywords

approximation algorithmprimal-dualpenalty costpower cover

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Packing and covering in (2) dimensions (aspects of discrete geometry) (52C15)

Cites Work

• Unnamed Item
• A unified approach to approximating partial covering problems
• A note on multicovering with disks
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• A primal-dual algorithm for the minimum power partial cover problem
• A note on the minimum power partial cover problem on the plane
• A primal-dual algorithm for the minimum partial set multi-cover problem
• Local ratio method on partial set multi-cover
• Minimum power partial multi-cover on a line
• Approximation algorithms for the minimum power cover problem with submodular/linear penalties
• A constant-factor approximation for multi-covering with disks
• On the Complexity of Numerical Analysis
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Algorithms – ESA 2005
• Approximation and Online Algorithms

This page was built for publication: An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem