MAX-CUT has a randomized approximation scheme in dense graphs

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-U" /><187::AID-RSA3>3.0.CO;2-U 10.1002/(SICI)1098-2418(199605)8:3<187::AID-RSA3>3.0.CO;2-UzbMath0848.90120OpenAlexW2109694798MaRDI QIDQ4885224

Wenceslas 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<187::aid-rsa3>3.0.co;2-u

zbMATH Keywords

randomized algorithmpolynomial timemaximum cut problemcut in a graph

Mathematics Subject Classification ID

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

Related Items (12)

On the efficiency of polynomial time approximation schemes ⋮ Random sampling and approximation of MAX-CSPs ⋮ Hardness of fully dense problems ⋮ Additive approximation for edge-deletion problems ⋮ Amplification and Derandomization without Slowdown ⋮ Introduction to Testing Graph Properties ⋮ Unnamed Item ⋮ Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION ⋮ Partitioning problems in dense hypergraphs ⋮ Introduction to Testing Graph Properties ⋮ Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems ⋮ A randomized approximation scheme for metric MAX-CUT

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