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

(27)

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

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)