The fundamental problem of distance geometry involves the characterization and study of sets of points based only on given values of some or all of the distances between pairs of points. This problem has a wide range of applications in various areas of mathe- matics, physics, chemistry, and engineering. Euclidean distance matrices play an important role in this context by providing elegant and powerful convex relaxations. They play an important role in problems such as graph realization and graph rigidity. Moreover, by relaxing the embedding dimension restriction, these matrices can be used to approximate the hard problems e‰ciently using semidefinite programming. Throughout this survey we emphasize the interplay between these concepts and problems. In addition, we illustrate this interplay in the context of the sensor network localization problem.

Alfakih, A., Anjos, M., Piccialli, V., Wolkowicz, H. (2011). Euclidean distance matrices, semidefinite programming, and sensor network localization (a survey). PORTUGALIAE MATHEMATICA, 68(1), 53-102 [10.4171/PM/1881].

Euclidean distance matrices, semidefinite programming, and sensor network localization (a survey)

PICCIALLI, VERONICA;
2011-01-01

Abstract

The fundamental problem of distance geometry involves the characterization and study of sets of points based only on given values of some or all of the distances between pairs of points. This problem has a wide range of applications in various areas of mathe- matics, physics, chemistry, and engineering. Euclidean distance matrices play an important role in this context by providing elegant and powerful convex relaxations. They play an important role in problems such as graph realization and graph rigidity. Moreover, by relaxing the embedding dimension restriction, these matrices can be used to approximate the hard problems e‰ciently using semidefinite programming. Throughout this survey we emphasize the interplay between these concepts and problems. In addition, we illustrate this interplay in the context of the sensor network localization problem.
2011
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore MAT/09 - RICERCA OPERATIVA
English
Senza Impact Factor ISI
Euclidean distance matrix completions; sensor network localization; fundamental problem of distance geometry; semidefinite programming
http://www.ems-ph.org/journals/show_abstract.php?issn=0032-5155&vol=68&iss=1&rank=4
Alfakih, A., Anjos, M., Piccialli, V., Wolkowicz, H. (2011). Euclidean distance matrices, semidefinite programming, and sensor network localization (a survey). PORTUGALIAE MATHEMATICA, 68(1), 53-102 [10.4171/PM/1881].
Alfakih, A; Anjos, M; Piccialli, V; Wolkowicz, H
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
PortugaliaeMathematica11.pdf

solo utenti autorizzati

Descrizione: Articolo come pubblicato
Licenza: Copyright dell'editore
Dimensione 594.57 kB
Formato Adobe PDF
594.57 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/70147
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 19
  • ???jsp.display-item.citation.isi??? 16
social impact