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

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

Fengmin Wang, Da-Chuan Xu, Dong-lei Du, 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 algorithmset coverprimal-dualpenaltiessubmodular cost

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A unified approach to approximating partial covering problems
• A note on the prize collecting traveling salesman problem
• A faster strongly polynomial time algorithm for submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• Submodular functions and optimization.
• Primal-Dual Approximation Algorithms for Submodular Vertex Cover Problems with Linear/Submodular Penalties
• The Design of Approximation Algorithms
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• The prize collecting traveling salesman problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Set Partitioning: A survey
• Covering, Packing and Knapsack Problems
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• Approximation algorithms for partial covering problems
• A General Approximation Technique for Constrained Forest Problems
• Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty
• Submodular Function Minimization under Covering Constraints