On approximation of max-vertex-cover

DOI10.1016/S0377-2217(02)00330-2zbMath1058.90036OpenAlexW2004973717MaRDI QIDQ1848386

Qiaoming Han, Yinyu Ye, Jia-Wei Zhang, Han-Tao Zhang

Publication date: 20 November 2002

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(02)00330-2

zbMATH Keywords

Linear programmingSemidefinite programmingPolynomial approximation algorithmMax-vertex-cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Linear programming (90C05) Interior-point methods (90C51)

Related Items

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix, Approximation algorithm for MAX DICUT with given sizes of parts, Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs, Approximation with a fixed number of solutions of some multiobjective maximization problems, Matroid-constrained vertex cover, Maximum Weighted Independent Sets with a Budget, Online maximum \(k\)-coverage, Maximizing coverage while ensuring fairness: a tale of conflicting objectives, Solving the maximum duo-preservation string mapping problem with linear programming, The maximum vertex coverage problem on bipartite graphs, Measuring the impact of MVC attack in large complex networks, Online Maximum k-Coverage, Improved approximation of maximum vertex cover

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• The hardness of approximation: Gap location
• Approximating the independence number via the \(\vartheta\)-function
• Approximating quadratic programming with bound and quadratic constraints
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• An improved rounding method and semidefinite programming relaxation for graph partition
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• Outward rotations
• Worst-Case and Probabilistic Analysis of Algorithms for a Location Problem
• 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
• Semidefinite relaxation and nonconvex quadratic optimization
• A .699-approximation algorithm for Max-Bisection.