Abstract
Distance Geometry puts the concept of distance at its center. The basic problem in distance geometry could be described as drawing an edge-weighted undirected graph in \(\mathbb {R}^K\) for some given K such that the positions for adjacent vertices have distance which is equal to the corresponding edge weight. There appears to be a lack of exact methods in this field using any other norm but \(\ell _2\). In this paper we move some first steps using the \(\ell _1\) and \(\ell _\infty \) norms: we discuss worst-case complexity, propose mixed-integer linear programming formulations, and sketch a few heuristic ideas.
L. Liberti—Partly supported by the ANR “Bip:Bip” project under contract ANR-10-BINF-0003.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Beeker, N., Gaubert, S., Glusa, C., Liberti, L.: Is the distance geometry problem in NP? In: Mucherino, A., Lavor, C., Liberti, L., Maculan, N. (eds.) Distance Geometry: Theory, Methods, and Applications. Springer, New York (2013)
Chiu, W.-Y., Chen, B.-S.: Mobile positioning problem in Manhattan-like urban areas: Uniqueness of solution, optimal deployment of BSs, and fuzzy implementation. IEEE Trans. Sig. Process. 57(12), 4918–4929 (2009)
COIN-OR. Introduction to IPOPT: A tutorial for downloading, installing, and using IPOPT (2006)
Crippen, G.M.: An alternative approach to distance geometry using \(\text{ L } \infty \) distances. Discrete Appl. Math. 197, 20–26 (2015). Distance Geometry and Applications
D’Ambrosio, C., Nannicini, G., Sartor, G.: MILP models for the selection of a small set of well-distributed points. Oper. Res. Lett. 45, 46–52 (2017)
D’Ambrosio, C., Vu, K., Lavor, C., Liberti, L., Maculan, N.: New error measures and methods for realizing protein graphs from distance data. Discrete Comput. Geom. 57(2), 371–418 (2017)
Dokmanić, I., Parhizkar, R., Ranieri, J., Vetterli, M.: Euclidean distance matrices: essential theory, algorithms and applications. IEEE Sig. Process. Mag. 1053–5888, 12–30 (2015)
Erdős, P., Rényi, A.: On random graphs i. Publ. Math. (Debrecen) 6, 290–297 (1959)
Fischetti, M., Lodi, A.: Local branching. Math. Program. 98, 23–37 (2005)
Fréchet, M.: Sur quelques points du calcul fonctionnel. Rend. Circ. Mat. Palermo 22, 1–74 (1906)
Gill, P.E.: User’s guide for SNOPT version 7.2. Systems Optimization Laboratory. Stanford University, California (2006)
Hansen, P., Mladenović, N.: Variable neighbourhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)
IBM: ILOG CPLEX 12.6 User’s Manual. IBM (2014)
Liberti, L., Lavor, C., Maculan, N., Mucherino, A.: Euclidean distance geometry and applications. SIAM Rev. 56(1), 3–69 (2014)
Matousek, J.: On the distortion required for embedding finite metric spaces into normed spaces. Isr. J. Math. 93, 333–344 (1996)
Matoušek, J.: Lecture notes on metric embeddings. Technical report, ETH Zürich (2013)
Mehlhorn, K., Sanders, P.: Algorithms and Data Structures. Springer, Berlin (2008)
Saxe, J.: Embeddability of weighted graphs in \(k\)-space is strongly NP-hard. In: Proceedings of 17th Allerton Conference in Communications, Control and Computing, pp. 480–489 (1979)
Vu, K., D’Ambrosio, C., Hamadi, Y., Liberti, L.: Surrogate-based methods for black-box optimization. Int. Trans. Oper. Res. 24(3), 393–424 (2017)
Wüthrich, K.: Protein structure determination in solution by nuclear magnetic resonance spectroscopy. Science 243, 45–50 (1989)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
D’Ambrosio, C., Liberti, L. (2017). Distance Geometry in Linearizable Norms. In: Nielsen, F., Barbaresco, F. (eds) Geometric Science of Information. GSI 2017. Lecture Notes in Computer Science(), vol 10589. Springer, Cham. https://doi.org/10.1007/978-3-319-68445-1_95
Download citation
DOI: https://doi.org/10.1007/978-3-319-68445-1_95
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68444-4
Online ISBN: 978-3-319-68445-1
eBook Packages: Computer ScienceComputer Science (R0)