MAX-CUT has a randomized approximation scheme in dense graphs

DOI10.1002/(SICI)1098-2418(199605)8:3%3C187::AID-RSA3%3E3.0.CO;2-UMaRDI QIDQ4885224zbMATH OpenOpenAlexFDO

Authors W. Fernandez de la Vega

Publication date 24 October 1996

Full work available at URL https://doi.org/10.1002/(sici)1098-2418(199605)8:3%3C187::aid-rsa3%3E3.0.co;2-u

zbMATH Keywords

randomized algorithmpolynomial timemaximum cut problemcut in a graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 2038711
• MAX CUT in cubic graphs
• scientific article; zbMATH DE number 1787231
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Improved approximation of Max-Cut on graphs of bounded degree

Cited in

(18)

• scientific article; zbMATH DE number 1496577 (Why is no real title available?)
• STACS 2005
• Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Partitioning problems in dense hypergraphs
• On the efficiency of polynomial time approximation schemes
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Local approximation of the maximum cut in regular graphs
• Random sampling and approximation of MAX-CSPs
• Approximating graph-constrained max-cut
• Additive approximation for edge-deletion problems
• Introduction to testing graph properties
• Introduction to testing graph properties
• Hardness of fully dense problems
• Solving Sparse Random Instances of Max Cut and Max 2-CSP in Linear Expected Time
• On the optimality of the random hyperplane rounding technique for MAX CUT
• A randomized approximation scheme for metric MAX-CUT
• Amplification and Derandomization without Slowdown

This page was built for publication: MAX-CUT has a randomized approximation scheme in dense graphs

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