A note on the submodular vertex cover problem with submodular penalties

DOI10.1016/J.TCS.2016.10.017zbMath1357.68295OpenAlexW2554369515MaRDI QIDQ730006

Naoyuki Kamiyama

Publication date: 23 December 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.10.017

zbMATH Keywords

vertex cover problemsubmodular functionsset cover problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)

Related Items (2)

Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

Cites Work

• Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Submodular Function Minimization under Covering Constraints

This page was built for publication: A note on the submodular vertex cover problem with submodular penalties