NP-hardness of the cluster minimization problem revisited

DOI10.1088/0305-4470/38/40/001zbMATH Open1075.68033OpenAlexW3101548220MaRDI QIDQ5699705FDOQ5699705

Authors Artur B. Adib 

Publication date 26 October 2005

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0509016

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Atomic physics (81V45)

Abstract: The computational complexity of the "cluster minimization problem" is revisited [L. T. Wille and J. Vennik, J. Phys. A 18, L419 (1985)]. It is argued that the original NP-hardness proof does not apply to pairwise potentials of physical interest, such as those that depend on the geometric distance between the particles. A geometric analog of the original problem is formulated, and a new proof for such potentials is provided by polynomial time transformation from the independent set problem for unit disk graphs. Limitations of this formulation are pointed out, and new subproblems that bear more direct consequences to the numerical study of clusters are suggested.

Recommendations

• NP-hardness of some max-min clustering problems
• NP-hardness of some quadratic Euclidean 2-clustering problems
• scientific article; zbMATH DE number 2081029
• NP-hardness of Euclidean sum-of-squares clustering
• scientific article; zbMATH DE number 3921982

Cited in

(7)

• On the hardness of energy minimisation for crystal structure prediction
• SOFSEM 2006: Theory and Practice of Computer Science
• Recent Advances in Constraints
• On the hardness of energy minimisation for crystal structure prediction
• Adaptive extremal optimization by detrended fluctuation analysis
• NP-hardness of Euclidean sum-of-squares clustering
• On the global minimum of the classical potential energy for clusters bound by many-body forces

This page was built for publication: NP-hardness of the cluster minimization problem revisited

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5699705)