Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
From MaRDI portal
Publication:278736
DOI10.1016/j.tcs.2016.04.005zbMath1338.90482OpenAlexW2338410001MaRDI QIDQ278736
Fengmin Wang, Da-Chuan Xu, Chen-Chen Wu, Dong-lei Du
Publication date: 2 May 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.04.005
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
An approximation algorithm for submodular hitting set problem with linear penalties ⋮ Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties ⋮ Approximation algorithms for the minimum power cover problem with submodular/linear penalties ⋮ Approximation algorithms for the submodular edge cover problem with submodular penalties ⋮ A note on the submodular vertex cover problem with submodular penalties ⋮ Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on the prize collecting traveling salesman problem
- Geometric algorithms and combinatorial optimization
- A push-relabel framework for submodular function minimization and applications to parametric optimization
- Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
- A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
- A primal-dual approximation algorithm for the facility location problem with submodular penalties
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Submodular functions and optimization.
- A better approximation ratio for the vertex cover problem
- An Extension of the Nemhauser–Trotter Theorem to Generalized Vertex Cover with Applications
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
- A linear-time approximation algorithm for the weighted vertex cover problem
- Approximation Algorithms for the Set Covering and Vertex Cover Problems
- Capacitated vertex covering
- A General Approximation Technique for Constrained Forest Problems
- Improved Approximation Algorithms for the Facility Location Problems with Linear/submodular Penalty
- Reducibility among Combinatorial Problems
- Submodular Function Minimization under Covering Constraints
- On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
