Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
DOI10.1016/j.disopt.2017.09.001zbMath1506.68067OpenAlexW2760699946MaRDI QIDQ1662108
Vangelis Th. Paschos, Édouard Bonnet, Bruno Escoffier, Georgios Stamoulis
Publication date: 17 August 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2017.09.001
Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On linear and semidefinite programming relaxations for hypergraph matching
- The hardness of approximation: Gap location
- On approximation of max-vertex-cover
- The maximum vertex coverage problem on bipartite graphs
- Approximating low-dimensional coverage problems
- Improved Approximation of Maximum Vertex Coverage Problem on Bipartite Graphs
- Greedy Algorithms for Steiner Forest
- Improved approximation of Max-Cut on graphs of bounded degree
- On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
- Minconvex Factors of Prescribed Size in Graphs
- Exceptional Paper—Location of Bank Accounts to Optimize Float: An Analytic Study of Exact and Approximate Algorithms
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Max cut and the smallest eigenvalue
- Tighter Bounds for Graph Steiner Tree Approximation
- Steiner Tree Approximation via Iterative Randomized Rounding
- Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection
This page was built for publication: Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
