A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem

DOI10.1007/s11590-021-01831-zzbMath1503.90116OpenAlexW3215399020MaRDI QIDQ2080830

Runtao Xie, Xiaofei Liu, Weidong Li

Publication date: 11 October 2022

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-021-01831-z

zbMATH Keywords

approximation algorithmprimal-dual\(k\)-prize-collectionpower cover

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (6)

Online mixed ring covering problem with two nodes ⋮ An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ The bound coverage problem by aligned disks in \(L_1\) metric ⋮ An improved approximation algorithm for the \(k\)-prize-collecting minimum power cover problem ⋮ An approximation algorithm for the \(H\)-prize-collecting power cover problem ⋮ Energy-constrained geometric coverage problem

Cites Work

• Improved performance of the greedy algorithm for partial cover
• Approximation algorithm for partial positive influence problem in social network
• Approximation algorithms for combinatorial problems
• Clustering to minimize the sum of cluster diameters
• A note on multicovering with disks
• Approximation algorithm for the partial set multi-cover problem
• Approximation algorithm for minimum power partial multi-coverage in wireless sensor networks
• An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem
• A bicriteria algorithm for the minimum submodular cost partial set multi-cover problem
• A primal-dual algorithm for the minimum partial set multi-cover problem
• Local ratio method on partial set multi-cover
• A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Fault-tolerant covering problems in metric spaces
• A constant-factor approximation for multi-covering with disks
• A Greedy Heuristic for the Set-Covering Problem
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• Algorithms – ESA 2005
• Approximation and Online Algorithms
• Unnamed Item
• Unnamed Item

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