An approximation algorithm for P-prize-collecting set cover problem

DOI10.1007/S40305-021-00364-7MaRDI QIDQ2687689zbMATH OpenOpenAlexFDO

Authors 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

\(P\)-prize-collecting set cover problemapproximation algorithmLagrangian relaxationprimal-dual

Mathematics Subject Classification ID

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

Recommendations

• A Unified Approach to Approximating Partial Covering Problems
• A unified approach to approximating partial covering problems
• Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties
• Approximation algorithm for stochastic set cover problem
• A bicriteria approximation algorithm for minimum submodular cost partial multi-cover problem

Cites work

• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A unified approach to approximating partial covering problems
• An approximation algorithm for the k-prize-collecting multicut on a tree problem
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for partial covering problems
• scientific article; zbMATH DE number 1757947 (Why is no real title available?)
• On approximation of the submodular set cover problem
• Partial multicuts in trees
• Set Partitioning: A survey
• The design of approximation algorithms
• Using homogeneous weights for approximating the partial cover problem

Cited in

(9)

• Approximation algorithm for the stochastic prize-collecting set multicover problem
• Prize‐collecting set multicovering with submodular pricing
• An approximation algorithm for the B-prize-collecting multicut problem in trees
• An approximation algorithm for the H-prize-collecting power cover problem
• The prize-collecting single machine scheduling with bounds and penalties
• W-prize-collecting with release dates on a single machine
• Approximation algorithms for the partition set cover problem with penalties
• Approximation algorithms for the W-prize-collecting scheduling problem on a single machine with submodular rejection penalties
• Approximation algorithm for the W-prize-collecting scheduling problem on a single machine with release dates and rejection

This page was built for publication: An approximation algorithm for \(P\)-prize-collecting set cover problem

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