scientific article; zbMATH DE number 1496577

DOI10.1002/1098-2418(200007)16:4%3C314::AID-RSA2%3E3.0.CO;2-EMaRDI QIDQ4500688zbMATH OpenFDO

Authors W. Fernandez de la Vega, Marek Karpinski

Publication date 27 August 2000

Full work available at URL https://doi.org/10.1002/1098-2418(200007)16:4%3C314::AID-RSA2%3E3.0.CO;2-E

zbMATH Keywords

approximation schemesdensity classesMAX-CUTrandomized algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1263204
• On the approximability of Max-Cut
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• Improved approximation algorithms for MAX k-CUT and MAX BISECTION

Cites work

• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• MAX-CUT has a randomized approximation scheme in dense graphs
• On the efficiency of polynomial time approximation schemes
• Optimization, approximation, and complexity classes
• Quick approximation to matrices and applications

Cited in

(6)

• A randomized approximation scheme for metric MAX-CUT
• Optimal cuts and partitions in tree metrics in polynomial time
• scientific article; zbMATH DE number 18532 (Why is no real title available?)
• scientific article; zbMATH DE number 1263204 (Why is no real title available?)
• Streaming Euclidean \textsc{Max-Cut}: dimension vs data reduction
• Exploiting dense structures in parameterized complexity

This page was built for publication:

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