A randomized approximation scheme for metric MAX-CUT

DOI10.1006/jcss.2001.1772zbMath1006.68164OpenAlexW2004328207MaRDI QIDQ1604207

Claire M. Kenyon, Wenceslas Fernandez de la Vega

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/038693646f90f089d377200429e72d724f7982c5

zbMATH Keywords

MAX-CUT

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (12)

Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ On the complexity of some quadratic Euclidean 2-clustering problems ⋮ Exact pseudopolynomial algorithms for a balanced 2-clustering problem ⋮ On Metric Clustering to Minimize the Sum of Radii ⋮ NP-hardness of some quadratic Euclidean 2-clustering problems ⋮ NP-hardness of the Euclidean Max-Cut problem ⋮ Polynomial-time approximation algorithm for the problem of cardinality-weighted variance-based 2-clustering with a given center ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ On metric clustering to minimize the sum of radii ⋮ Min sum clustering with penalties ⋮ Unnamed Item ⋮ Complexity of the weighted max-cut in Euclidean space

Cites Work

• Combinatorial properties and the complexity of a max-cut approximation
• On clustering problems with connected optima in Euclidean spaces
• Quick approximation to matrices and applications
• Optimization, approximation, and complexity classes
• Laplacian eigenvalues and the maximum cut problem
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Proof verification and the hardness of approximation problems
• Finding tailored partitions
• Geometric clusterings
• P-Complete Approximation Problems
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• MAX-CUT has a randomized approximation scheme in dense graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A randomized approximation scheme for metric MAX-CUT