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

DOI10.3934/naco.2015.5.91zbMath1317.90260MaRDI QIDQ2353460

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

Publication date: 14 July 2015

Published in: Numerical Algebra, Control and Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3934/naco.2015.5.91

zbMATH Keywords

approximation algorithm; set cover; primal-dual; penalties; submodular cost

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization