Search Results

Documents authored by Khodabandeh, Hadi

Document
DOI: 10.4230/LIPIcs.DISC.2022.21
Distributed Construction of Lightweight Spanners for Unit Ball Graphs

Authors: David Eppstein and Hadi Khodabandeh

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
Resolving an open question from 2006 [Damian et al., 2006], we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple 𝒪(log^*n)-round distributed algorithm in the LOCAL model of computation, that given a unit ball graph G with n vertices and a positive constant ε < 1 finds a (1+ε)-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the best prior lightness bound, the algorithm of Damian, Pandit, and Pemmaraju [Damian et al., 2006], which runs in 𝒪(log^*n) rounds in the LOCAL model, but has a 𝒪(log Δ) bound on its lightness, where Δ is the ratio of the length of the longest edge to the length of the shortest edge in the unit ball graph. Next, we adjust our algorithm to work in the CONGEST model, without changing its round complexity, hence proposing the first spanner construction for unit ball graphs in the CONGEST model of computation. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersections per node. Lastly, we provide experimental results that confirm our theoretical bounds, and show an efficient performance from our distributed algorithm compared to the best known centralized construction.
Cite as

David Eppstein and Hadi Khodabandeh. Distributed Construction of Lightweight Spanners for Unit Ball Graphs. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.DISC.2022.21,
  author =	{Eppstein, David and Khodabandeh, Hadi},
  title =	{{Distributed Construction of Lightweight Spanners for Unit Ball Graphs}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{21:1--21:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.21},
  URN =		{urn:nbn:de:0030-drops-172129},
  doi =		{10.4230/LIPIcs.DISC.2022.21},
  annote =	{Keywords: spanners, doubling metrics, distributed, topology control}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.18
Online Spanners in Metric Spaces

Authors: Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂-norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)-spanner algorithm with competitive ratio O_d(ε^{-d} log n), improving the previous bound of O_d(ε^{-(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{-3/2}logε^{-1}log n), by comparing the online spanner with an instance-optimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{-d}) lower bound for the competitive ratio for online (1+ε)-spanner algorithms in ℝ^d under the L₁-norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k-1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{-1}logε^{-1})⋅ n^{1+1/k} edges and O(ε^{-1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the trade-off among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)-spanner for ultrametrics with O(ε^{-1}logε^{-1})⋅ n edges and O(ε^{-2}) lightness.
Cite as

Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth. Online Spanners in Metric Spaces. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ESA.2022.18,
  author =	{Bhore, Sujoy and Filtser, Arnold and Khodabandeh, Hadi and T\'{o}th, Csaba D.},
  title =	{{Online Spanners in Metric Spaces}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.18},
  URN =		{urn:nbn:de:0030-drops-169564},
  doi =		{10.4230/LIPIcs.ESA.2022.18},
  annote =	{Keywords: spanner, online algorithm, lightness, sparsity, minimum weight}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.33
On the Edge Crossings of the Greedy Spanner

Authors: David Eppstein and Hadi Khodabandeh

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
The greedy t-spanner of a set of points in the plane is an undirected graph constructed by considering pairs of points in order by distance, and connecting a pair by an edge when there does not already exist a path connecting that pair with length at most t times the Euclidean distance. We prove that, for any t > 1, these graphs have at most a linear number of crossings, and more strongly that the intersection graph of edges in a greedy t-spanner has bounded degeneracy. As a consequence, we prove a separator theorem for greedy spanners: any k-vertex subgraph of a greedy spanner can be partitioned into sub-subgraphs of size a constant fraction smaller, by the removal of O(√k) vertices. A recursive separator hierarchy for these graphs can be constructed from their planarizations in linear time, or in near-linear time if the planarization is unknown.
Cite as

David Eppstein and Hadi Khodabandeh. On the Edge Crossings of the Greedy Spanner. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:LIPIcs.SoCG.2021.33,
  author =	{Eppstein, David and Khodabandeh, Hadi},
  title =	{{On the Edge Crossings of the Greedy Spanner}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.33},
  URN =		{urn:nbn:de:0030-drops-138328},
  doi =		{10.4230/LIPIcs.SoCG.2021.33},
  annote =	{Keywords: Geometric Spanners, Greedy Spanners, Separators, Crossing Graph, Sparsity}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact