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-UzbMATH Open0848.90120OpenAlexW2109694798MaRDI QIDQ4885224FDOQ4885224
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
Recommendations
Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Abstract computational complexity for mathematical programming problems (90C60)
Cited In (18)
- STACS 2005
- Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold
- Partitioning problems in dense hypergraphs
- Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- On the efficiency of polynomial time approximation schemes
- 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
- Title not available (Why is that?)
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)
