DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2024.9

Freeze-Tag in L₁ Has Wake-Up Time Five with Linear Complexity

Authors: Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, and Nicolas Hanusse

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract

The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of n robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the makespan of the last robot, the makespan. Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the 𝓁₁-norm, showing that a makespan of at most 5r can always be achieved, where r is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most 5r can be computed in time O(n). Both bounds, the time and the makespan are optimal. Our results also imply for the 𝓁₂-norm a new upper bound of 5√2r ≈ 7.07r on the makespan, improving the best known bound of (5+2√2+√5)r ≈ 10.06r. Along the way, we introduce new linear time wake-up strategies, that apply to any norm and show that an optimal bound on the makespan can always be achieved by a schedule computable in linear time.

Cite as

Nicolas Bonichon, Arnaud Casteigts, Cyril Gavoille, and Nicolas Hanusse. Freeze-Tag in L₁ Has Wake-Up Time Five with Linear Complexity. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bonichon_et_al:LIPIcs.DISC.2024.9,
  author =	{Bonichon, Nicolas and Casteigts, Arnaud and Gavoille, Cyril and Hanusse, Nicolas},
  title =	{{Freeze-Tag in L₁ Has Wake-Up Time Five with Linear Complexity}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.9},
  URN =		{urn:nbn:de:0030-drops-212356},
  doi =		{10.4230/LIPIcs.DISC.2024.9},
  annote =	{Keywords: freeze-tag problem, metric, algorithm}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2020.11

Framing Algorithms for Approximate Multicriteria Shortest Paths

Authors: Nicolas Hanusse, David Ilcinkas, and Antonin Lentz

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract

This paper deals with the computation of d-dimensional multicriteria shortest paths. In a weighted graph with arc weights represented by vectors, the cost of a path is the vector sum of the weights of its arcs. For a given pair consisting of a source s and a destination t, a path P dominates a path Q if and only if P’s cost is component-wise smaller than or equal to Q’s cost. The set of Pareto paths, or Pareto set, from s to t is the set of paths that are not dominated. The computation time of the Pareto paths can be prohibitive whenever the set of Pareto paths is large. We propose in this article new algorithms to compute approximated Pareto paths in any dimension. For d = 2, we exhibit the first approximation algorithm, called Frame, whose output is guaranteed to be always a subset of the Pareto set. Finally, we provide a small experimental study in order to confirm the relevance of our Frame algorithm.

Cite as

Nicolas Hanusse, David Ilcinkas, and Antonin Lentz. Framing Algorithms for Approximate Multicriteria Shortest Paths. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hanusse_et_al:OASIcs.ATMOS.2020.11,
  author =	{Hanusse, Nicolas and Ilcinkas, David and Lentz, Antonin},
  title =	{{Framing Algorithms for Approximate Multicriteria Shortest Paths}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{11:1--11:19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.11},
  URN =		{urn:nbn:de:0030-drops-131476},
  doi =		{10.4230/OASIcs.ATMOS.2020.11},
  annote =	{Keywords: Pareto set, multicriteria, shortest paths, approximation}
}

Search Results

Documents authored by Hanusse, Nicolas

Freeze-Tag in L₁ Has Wake-Up Time Five with Linear Complexity

Abstract

Cite as

Framing Algorithms for Approximate Multicriteria Shortest Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message