NP-hardness of the Euclidean Max-Cut problem
From MaRDI portal
Publication:471386
DOI10.1134/S1064562414030235zbMath1307.90212OpenAlexW2000311458MaRDI QIDQ471386
A. A. Ageev, Artem V. Pyatkin, Alexander Kel'Manov
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
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items (7)
Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ On the complexity of some quadratic Euclidean 2-clustering problems ⋮ 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 ⋮ A randomized algorithm for two-cluster partition of a set of vectors
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of a search for a subset of ``similar vectors
- Some simplified NP-complete graph problems
- A randomized approximation scheme for metric MAX-CUT
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Data Collection for the Sloan Digital Sky Survey—A Network-Flow Heuristic
- Estimation of Distribution Algorithm for the Max-Cut Problem
- Reducibility among Combinatorial Problems
This page was built for publication: NP-hardness of the Euclidean Max-Cut problem