On the approximability of Max-Cut

zbMATH Open1122.68064MaRDI QIDQ873802FDOQ873802

Le Cong Thanh

Publication date: 20 March 2007

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

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

zbMATH Keywords

absolute performance ratio

Mathematics Subject Classification ID

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

Cited In (26)

• Use of MAX-CUT for Ramsey Arrowing of Triangles
• Approximating \(\alpha\)-cuts with the vertex method
• Rank of Handelman hierarchy for Max-Cut
• On complexity of the translational-cut algorithm for convex minimax problems
• On the complexity of finding balanced oneway cuts
• Title not available (Why is that?)
• The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximum cuts: Improvements and local algorithmic analogues of the Edwards-Erdős inequality
• Optimal Bounds for the k -cut Problem
• Approximating graph-constrained max-cut
• Approximation algorithms for requirement cut on graphs
• Algorithms – ESA 2005
• Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3
• Node and edge relaxations of the max-cut problem
• Streaming Lower Bounds for Approximating MAX-CUT
• Title not available (Why is that?)
• Approximation algorithms for connected maximum cut and related problems
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• On the optimality of the random hyperplane rounding technique for MAX CUT
• 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
• A randomized approximation scheme for metric MAX-CUT
• From Graph Orientation to the Unweighted Maximum 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)