On the approximability of Max-Cut

MaRDI QIDQ873802zbMATH OpenFDO

Authors Le Cong Thanh

Publication date 20 March 2007

Published in Vietnam Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

absolute performance ratio

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• How Good is the Goemans--Williamson MAX CUT Algorithm?
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• scientific article; zbMATH DE number 1256761

Cited in

(28)

• On the complexity of finding balanced oneway cuts
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Approximating -cuts with the vertex method
• Node and edge relaxations of the max-cut problem
• A randomized approximation scheme for metric MAX-CUT
• Approximating graph-constrained max-cut
• The expected relative error of the polyhedral approximation of the max- cut problem
• From Graph Orientation to the Unweighted Maximum Cut
• On the practically interesting instances of MAXCUT
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• Rank of Handelman hierarchy for Max-Cut
• scientific article; zbMATH DE number 1304324 (Why is no real title available?)
• scientific article; zbMATH DE number 1496577 (Why is no real title available?)
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Optimal Bounds for the k -cut Problem
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Streaming Lower Bounds for Approximating MAX-CUT
• Use of MAX-CUT for Ramsey Arrowing of Triangles
• scientific article; zbMATH DE number 5232308 (Why is no real title available?)
• Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 7650221 (Why is no real title available?)
• On complexity of the translational-cut algorithm for convex minimax problems
• scientific article; zbMATH DE number 7724211 (Why is no real title available?)
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Approximation algorithms for requirement cut on graphs

This page was built for publication: On the approximability of Max-Cut

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q873802)