Search Results

Documents authored by Sitters, René

Document
DOI: 10.4230/LIPIcs.MFCS.2023.86
Exact and Approximation Algorithms for Routing a Convoy Through a Graph

Authors: Martijn van Ee, Tim Oosterwijk, René Sitters, and Andreas Wiese

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study routing problems of a convoy in a graph, generalizing the shortest path problem (SPP), the travelling salesperson problem (TSP), and the Chinese postman problem (CPP) which are all well-studied in the classical (non-convoy) setting. We assume that each edge in the graph has a length and a speed at which it can be traversed and that our convoy has a given length. While the convoy moves through the graph, parts of it can be located on different edges. For safety requirements, at all time the whole convoy needs to travel at the same speed which is dictated by the slowest edge on which currently a part of the convoy is located. For Convoy-SPP, we give a strongly polynomial time exact algorithm. For Convoy-TSP, we provide an O(log n)-approximation algorithm and an O(1)-approximation algorithm for trees. Both results carry over to Convoy-CPP which - maybe surprisingly - we prove to be NP-hard in the convoy setting. This contrasts the non-convoy setting in which the problem is polynomial time solvable.
Cite as

Martijn van Ee, Tim Oosterwijk, René Sitters, and Andreas Wiese. Exact and Approximation Algorithms for Routing a Convoy Through a Graph. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanee_et_al:LIPIcs.MFCS.2023.86,
  author =	{van Ee, Martijn and Oosterwijk, Tim and Sitters, Ren\'{e} and Wiese, Andreas},
  title =	{{Exact and Approximation Algorithms for Routing a Convoy Through a Graph}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{86:1--86:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.86},
  URN =		{urn:nbn:de:0030-drops-186205},
  doi =		{10.4230/LIPIcs.MFCS.2023.86},
  annote =	{Keywords: approximation algorithms, convoy routing, shortest path problem, traveling salesperson problem}
}
Document
DOI: 10.4230/DagSemProc.10071.3
10071 Open Problems – Scheduling

Authors: Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger

Published in: Dagstuhl Seminar Proceedings, Volume 10071, Scheduling (2010)

Abstract
Collection of the open problems presented at the scheduling seminar.
Cite as

Jim Anderson, Björn Andersson, Yossi Azar, Nikhil Bansal, Enrico Bini, Marek Chrobak, José Correa, Liliana Cucu-Grosjean, Rob Davis, Arvind Easwaran, Jeff Edmonds, Shelby Funk, Sathish Gopalakrishnan, Han Hoogeveen, Claire Mathieu, Nicole Megow, Seffi Naor, Kirk Pruhs, Maurice Queyranne, Adi Rosén, Nicolas Schabanel, Jiří Sgall, René Sitters, Sebastian Stiller, Marc Uetz, Tjark Vredeveld, and Gerhard J. Woeginger. 10071 Open Problems – Scheduling. In Scheduling. Dagstuhl Seminar Proceedings, Volume 10071, pp. 1-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{anderson_et_al:DagSemProc.10071.3,
  author =	{Anderson, Jim and Andersson, Bj\"{o}rn and Azar, Yossi and Bansal, Nikhil and Bini, Enrico and Chrobak, Marek and Correa, Jos\'{e} and Cucu-Grosjean, Liliana and Davis, Rob and Easwaran, Arvind and Edmonds, Jeff and Funk, Shelby and Gopalakrishnan, Sathish and Hoogeveen, Han and Mathieu, Claire and Megow, Nicole and Naor, Seffi and Pruhs, Kirk and Queyranne, Maurice and Ros\'{e}n, Adi and Schabanel, Nicolas and Sgall, Ji\v{r}{\'\i} and Sitters, Ren\'{e} and Stiller, Sebastian and Uetz, Marc and Vredeveld, Tjark and Woeginger, Gerhard J.},
  title =	{{10071 Open Problems – Scheduling}},
  booktitle =	{Scheduling},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{10071},
  editor =	{Susanne Albers and Sanjoy K. Baruah and Rolf H. M\"{o}hring and Kirk Pruhs},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10071.3},
  URN =		{urn:nbn:de:0030-drops-25367},
  doi =		{10.4230/DagSemProc.10071.3},
  annote =	{Keywords: Open problems, scheduling}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2458
The Traveling Salesman Problem under Squared Euclidean Distances

Authors: Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff, and Mark de Berg

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
Let $P$ be a set of points in $\Reals^d$, and let $\alpha \ge 1$ be a real number. We define the distance between two points $p,q\in P$ as $|pq|^{\alpha}$, where $|pq|$ denotes the standard Euclidean distance between $p$ and $q$. We denote the traveling salesman problem under this distance function by \tsp($d,\alpha$). We design a 5-approximation algorithm for \tsp(2,2) and generalize this result to obtain an approximation factor of $3^{\alpha-1}+\sqrt{6}^{\,\alpha}\!/3$ for $d=2$ and all $\alpha\ge2$. We also study the variant Rev-\tsp\ of the problem where the traveling salesman is allowed to revisit points. We present a polynomial-time approximation scheme for Rev-\tsp$(2,\alpha)$ with $\alpha\ge2$, and we show that Rev-\tsp$(d, \alpha)$ is \apx-hard if $d\ge3$ and $\alpha>1$. The \apx-hardness proof carries over to \tsp$(d, \alpha)$ for the same parameter ranges.
Cite as

Fred van Nijnatten, René Sitters, Gerhard J. Woeginger, Alexander Wolff, and Mark de Berg. The Traveling Salesman Problem under Squared Euclidean Distances. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 239-250, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{vannijnatten_et_al:LIPIcs.STACS.2010.2458,
  author =	{van Nijnatten, Fred and Sitters, Ren\'{e} and Woeginger, Gerhard J. and Wolff, Alexander and de Berg, Mark},
  title =	{{The Traveling Salesman Problem under Squared Euclidean Distances}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{239--250},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2458},
  URN =		{urn:nbn:de:0030-drops-24580},
  doi =		{10.4230/LIPIcs.STACS.2010.2458},
  annote =	{Keywords: Geometric traveling salesman problem, power-assignment in wireless networks, distance-power gradient, NP-hard, APX-hard}
}
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