An approximation algorithm for \(P\)-prize-collecting set cover problem

DOI10.1007/s40305-021-00364-7OpenAlexW3194671897MaRDI QIDQ2687689

Yanyan Li

Publication date: 7 March 2023

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40305-021-00364-7

zbMATH Keywords

Lagrangian relaxationapproximation algorithmprimal-dual\(P\)-prize-collecting set cover problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Approximation algorithms (68W25)

Related Items

An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees ⋮ An approximation algorithm for the \(H\)-prize-collecting power cover problem

Cites Work

• Unnamed Item
• A unified approach to approximating partial covering problems
• Partial multicuts in trees
• On approximation of the submodular set cover problem
• An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• The Design of Approximation Algorithms
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A linear-time approximation algorithm for the weighted vertex cover problem
• Set Partitioning: A survey
• Approximation algorithms for partial covering problems