Distance geometry in linearizable norms

Claudia D’Ambrosio; Leo Liberti

doi:10.1007/978-3-319-68445-1_95

Distance geometry in linearizable norms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 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 ℓ₂. In this paper we move some first steps using the ℓ₁ and ℓ_∞ norms: we discuss worst-case complexity, propose mixed-integer linear programming formulations, and sketch a few heuristic ideas.

Original language	English
Title of host publication	Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings
Editors	Frank Nielsen, Frederic Barbaresco, Frank Nielsen
Publisher	Springer Verlag
Pages	830-837
Number of pages	8
ISBN (Print)	9783319684444
DOIs	https://doi.org/10.1007/978-3-319-68445-1_95
Publication status	Published - 1 Jan 2017
Event	3rd International Conference on Geometric Science of Information, GSI 2017 - Paris, France Duration: 7 Nov 2017 → 9 Nov 2017

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10589 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	3rd International Conference on Geometric Science of Information, GSI 2017
Country/Territory	France
City	Paris
Period	7/11/17 → 9/11/17

Keywords

Distance geometry
Mathematical programming
Norms

Access to Document

10.1007/978-3-319-68445-1_95

Cite this

D’Ambrosio, C., & Liberti, L. (2017). Distance geometry in linearizable norms. In F. Nielsen, F. Barbaresco, & F. Nielsen (Eds.), Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings (pp. 830-837). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10589 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-68445-1_95

D’Ambrosio, Claudia ; Liberti, Leo. / Distance geometry in linearizable norms. Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings. editor / Frank Nielsen ; Frederic Barbaresco ; Frank Nielsen. Springer Verlag, 2017. pp. 830-837 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c7972bbe32e64bd99f3d3a95b7f3f179,

title = "Distance geometry in linearizable norms",

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 RK 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 ℓ2. In this paper we move some first steps using the ℓ1 and ℓ∞ norms: we discuss worst-case complexity, propose mixed-integer linear programming formulations, and sketch a few heuristic ideas.",

keywords = "Distance geometry, Mathematical programming, Norms",

author = "Claudia D{\textquoteright}Ambrosio and Leo Liberti",

note = "Publisher Copyright: {\textcopyright} 2017, Springer International Publishing AG.; 3rd International Conference on Geometric Science of Information, GSI 2017 ; Conference date: 07-11-2017 Through 09-11-2017",

year = "2017",

month = jan,

day = "1",

doi = "10.1007/978-3-319-68445-1\_95",

language = "English",

isbn = "9783319684444",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "830--837",

editor = "Frank Nielsen and Frederic Barbaresco and Frank Nielsen",

booktitle = "Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings",

}

D’Ambrosio, C & Liberti, L 2017, Distance geometry in linearizable norms. in F Nielsen, F Barbaresco & F Nielsen (eds), Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10589 LNCS, Springer Verlag, pp. 830-837, 3rd International Conference on Geometric Science of Information, GSI 2017, Paris, France, 7/11/17. https://doi.org/10.1007/978-3-319-68445-1_95

Distance geometry in linearizable norms. / D’Ambrosio, Claudia ; Liberti, Leo.
Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings. ed. / Frank Nielsen; Frederic Barbaresco; Frank Nielsen. Springer Verlag, 2017. p. 830-837 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10589 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Distance geometry in linearizable norms

AU - D’Ambrosio, Claudia

AU - Liberti, Leo

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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 RK 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 ℓ2. In this paper we move some first steps using the ℓ1 and ℓ∞ norms: we discuss worst-case complexity, propose mixed-integer linear programming formulations, and sketch a few heuristic ideas.

AB - 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 RK 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 ℓ2. In this paper we move some first steps using the ℓ1 and ℓ∞ norms: we discuss worst-case complexity, propose mixed-integer linear programming formulations, and sketch a few heuristic ideas.

KW - Distance geometry

KW - Mathematical programming

KW - Norms

UR - https://www.scopus.com/pages/publications/85033714128

U2 - 10.1007/978-3-319-68445-1_95

DO - 10.1007/978-3-319-68445-1_95

M3 - Conference contribution

AN - SCOPUS:85033714128

SN - 9783319684444

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 830

EP - 837

BT - Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings

A2 - Nielsen, Frank

A2 - Barbaresco, Frederic

A2 - Nielsen, Frank

PB - Springer Verlag

T2 - 3rd International Conference on Geometric Science of Information, GSI 2017

Y2 - 7 November 2017 through 9 November 2017

ER -

D’Ambrosio C , Liberti L. Distance geometry in linearizable norms. In Nielsen F, Barbaresco F, Nielsen F, editors, Geometric Science of Information - 3rd International Conference, GSI 2017, Proceedings. Springer Verlag. 2017. p. 830-837. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-68445-1_95

Distance geometry in linearizable norms

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this