Barvinok’s naive algorithm in Distance Geometry
| Autor: | Leo Liberti, Ky Khac Vu |
|---|---|
| Přispěvatelé: | Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X) |
| Rok vydání: | 2018 |
| Předmět: |
Quadratic growth
021103 operations research Heuristic (computer science) Applied Mathematics MathematicsofComputing_NUMERICALANALYSIS 0211 other engineering and technologies [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] 02 engineering and technology Management Science and Operations Research concentration of measure Industrial and Manufacturing Engineering Distance geometry Randomized algorithm Set (abstract data type) Matrix (mathematics) Naive algorithm ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0202 electrical engineering electronic engineering information engineering Applied mathematics 020201 artificial intelligence & image processing Relaxation (approximation) protein structure distance geometry Software Mathematics |
| Zdroj: | Operations Research Letters Operations Research Letters, Elsevier, 2018, 46 (5), pp.476-481. ⟨10.1016/j.orl.2018.06.006⟩ |
| ISSN: | 0167-6377 |
| DOI: | 10.1016/j.orl.2018.06.006 |
| Popis: | International audience; In 1997, A. Barvinok gave a probabilistic algorithm to derive a near-feasible solution of a quadratically (equation) constrained problem from its semidefinite relaxation. We generalize this algorithm to handle matrix variables instead of vectors, and to two-sided inequalities instead of equations. We derive a heuristic for the distance geometry problem, and showcase its computational performance on a set of instances related to protein conformation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect