Skip to main content
Erschienen in:
Buchtitelbild

2012 | OriginalPaper | Buchkapitel

Space Lower Bounds for Low-Stretch Greedy Embeddings

verfasst von : Ioannis Caragiannis, Christos Kalaitzis

Erschienen in: Structural Information and Communication Complexity

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Greedy (geometric) routing is an important paradigm for routing in communication networks. It uses an embedding of the nodes of the network into points of a metric space (e.g.,

) equipped with a distance function (e.g., the Euclidean distance ℓ

2

) and uses as address of each node the coordinates of the corresponding point. The embedding has particular properties so that the routing decision for a packet is taken greedily based only on the addresses of the current node, its neighbors, and the destination node and the distances of the corresponding points. In this way, there is no need to keep routing tables at the nodes. Embeddings that allow for this functionality are called greedy embeddings. Even though greedy embeddings do exist for several metric spaces and distance functions, they usually result in paths of high stretch, i.e., significantly longer than the corresponding shortest paths.

In this paper, we show that greedy embeddings in low-dimensional Euclidean spaces necessarily have high stretch. In particular, greedy embeddings of

n

-node graphs with optimal stretch requires at least Ω(

n

) dimensions for distance ℓ

2

. This result disproves a conjecture by Maymounkov (2006) stating that greedy embeddings of optimal stretch are possible in Euclidean spaces with polylogarithmic number of dimensions. Furthermore, we present trade-offs between the stretch and the number of dimensions of the host Euclidean space. Our results imply that every greedy embedding into a Euclidean space with polylogarithmic number of dimensions (and Euclidean distance) has stretch

$\Omega\left(\frac{\log n}{\log\log n}\right)$

. We extend this result for a distance function used by an

O

(log

n

)-stretch greedy embedding presented by Flury, Pemmaraju, and Wattenhofer (2009). Our lower bound implies that their embedding has almost best possible stretch.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Space Lower Bounds for Low-Stretch Greedy Embeddings
verfasst von
Ioannis Caragiannis
Christos Kalaitzis
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-31104-8_1

Premium Partner