1 Search Results for "Hanusse, Nicolas"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Hanusse, Nicolas
  • 1 Ilcinkas, David
  • 1 Lentz, Antonin

  • Refine by Classification
  • 1 Applied computing → Multi-criterion optimization and decision-making
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Pareto set
  • 1 approximation
  • 1 multicriteria
  • 1 shortest paths

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

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