NP-hardness of the Euclidean Max-Cut problem

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

zbMATH Keywords

Euclidean spacelengths of the edges

Mathematics Subject Classification ID

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