NP-hardness of the Euclidean Max-Cut problem
From MaRDI portal
Publication:471386
DOI10.1134/S1064562414030235zbMATH Open1307.90212OpenAlexW2000311458MaRDI QIDQ471386FDOQ471386
Authors: Alexander Ageev, A. V. Kel'manov, Artem Pyatkin 
Publication date: 14 November 2014
Published in: Doklady Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1134/s1064562414030235
Recommendations
Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)
Cites Work
- Title not available (Why is that?)
- Reducibility among combinatorial problems
- Some simplified NP-complete graph problems
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- On the complexity of a search for a subset of ``similar vectors
- Title not available (Why is that?)
- A randomized approximation scheme for metric MAX-CUT
- Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
- Title not available (Why is that?)
- Estimation of distribution algorithm for the max-cut problem
Cited In (10)
- A randomized algorithm for two-cluster partition of a set of vectors
- Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems
- Complexity and polynomially solvable special cases of QUBO
- MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
- Complexity of the weighted max-cut in Euclidean space
- An exact pseudopolynomial algorithm for a problem of the two-cluster partitioning of a set of vectors
- NP-hardness of some quadratic Euclidean 2-clustering problems
- On the hardness of energy minimisation for crystal structure prediction
- Computational complexity of diagram satisfaction in Euclidean geometry
- On the complexity of some quadratic Euclidean 2-clustering problems
This page was built for publication: NP-hardness of the Euclidean Max-Cut problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471386)
