Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties

DOI10.1007/978-3-319-08783-2_29zbMath1338.90481OpenAlexW1750858516MaRDI QIDQ2920471

Fengmin Wang, Dong-lei Du, Da-Chuan Xu, Chen-Chen Wu

Publication date: 26 September 2014

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-08783-2_29

zbMATH Keywords

submodular functionprimal-dual approximation algorithmsubmodular vertex cover problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) 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 (1)

Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties

This page was built for publication: Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties