NP-hardness of the cluster minimization problem revisited
From MaRDI portal
Publication:5699705
DOI10.1088/0305-4470/38/40/001zbMATH Open1075.68033arXivcs/0509016OpenAlexW3101548220MaRDI QIDQ5699705FDOQ5699705
Authors: Artur B. Adib 
Publication date: 26 October 2005
Published in: Journal of Physics A: Mathematical and General (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/cs/0509016
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Atomic physics (81V45)
Cited In (7)
- On the hardness of energy minimisation for crystal structure prediction
- Adaptive extremal optimization by detrended fluctuation analysis
- Recent Advances in Constraints
- On the global minimum of the classical potential energy for clusters bound by many-body forces
- On the hardness of energy minimisation for crystal structure prediction
- SOFSEM 2006: Theory and Practice of Computer Science
- NP-hardness of Euclidean sum-of-squares clustering
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)
