Approximation algorithm for vertex cover with multiple covering constraints

DOI10.1007/S00453-021-00885-WMaRDI QIDQ2072095zbMATH OpenOpenAlexFDO

Authors Eunpyeong Hung, Mong-Jen Kao

Publication date 1 February 2022

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/9991/

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Recommendations

• Approximation algorithm for vertex cover with multiple covering constraints
• Improved algorithms for vertex cover with hard capacities on multigraphs and hypergraphs
• A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
• Tight approximation for partial vertex cover with hard capacities
• Approximation algorithms for the partition vertex cover problem

Cites work

• scientific article; zbMATH DE number 1182766 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
• An analysis of the greedy algorithm for the submodular set covering problem
• Approximation algorithms for partial covering problems
• Approximation algorithms for the partition vertex cover problem
• Covering Problems with Hard Capacities
• On approximation of the submodular set cover problem
• Using homogeneous weights for approximating the partial cover problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(10)

• Combining Two Worlds: Parameterised Approximation for Vertex Cover
• Vertex cover meets scheduling
• Matroid-constrained vertex cover
• Approximation algorithms for the partition set cover problem with penalties
• Minimum-cost mixed graph covers with targeted weight constraints
• Approximation algorithm for vertex cover with multiple covering constraints
• Approximation algorithm for prize-collecting hypergraph vertex cover with fairness constraints
• Satisfiability to coverage in presence of fairness, matroid, and global constraints
• On generalizations of partial scenario set cover
• Approximation algorithm for prize-collecting vertex cover with fairness constraints

This page was built for publication: Approximation algorithm for vertex cover with multiple covering constraints

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