An approximation algorithm for the k-prize-collecting hitting set problem

DOI10.1007/S11590-024-02155-4MaRDI QIDQ6968702zbMATH OpenFDO

Authors Qin Liu, Bo Hou, Gengsheng Zhang, Wen Liu

Publication date 24 June 2025

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S11590-024-02155-4

zbMATH Keywords

greedyhitting set problemLP roundingpartialprize-collecting

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx) Mathematical programming (90Cxx)

Cites work

• A 4-approximation algorithm for k-prize collecting Steiner tree problems
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• A fast approximation algorithm for the multicovering problem
• A linear-time approximation algorithm for the weighted vertex cover problem
• A new polynomial-time algorithm for linear programming
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• A theory of diagnosis from first principles
• An approximation algorithm for the k-prize-collecting multicut on a tree problem
• An approximation algorithm for the partial covering 0-1 integer program
• Approximate Set Covering in Uniform Hypergraphs
• Approximation algorithms for partial covering problems
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Characterizing diagnoses and systems
• Geometric discrepancy. An illustrated guide
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• New and improved bounds for the minimum set cover problem
• New constructions of weak -nets
• On approximation of the vertex cover problem in hypergraphs
• Reducibility among combinatorial problems
• The minimal hitting set generation problem: algorithms and computation
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

This page was built for publication: An approximation algorithm for the \(k\)-prize-collecting hitting set problem

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