Complexity of the weighted max-cut in Euclidean space

DOI10.1134/S1990478914040012zbMath1324.05188OpenAlexW2037094620MaRDI QIDQ5264746

A. A. Ageev, Alexander Kel'Manov, Artem V. Pyatkin

Publication date: 27 July 2015

Published in: Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1990478914040012

zbMATH Keywords

Euclidean spacecutNP-hard problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (3)

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 ⋮ NP-hardness of some quadratic Euclidean 2-clustering problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On complexity of some problems of cluster analysis of vector sequences

This page was built for publication: Complexity of the weighted max-cut in Euclidean space