HAL TEI export of hal-04208894 CCSD CC0 1.0 - Universal

HAL API Platform

 Online TSP with Known Locations Evripidis Bampis 86302bba886873f656fe083cf63d42ea ibisc.univ-evry.fr 1284586 145111-1284586 https://orcid.org/0000-0002-4498-3040 https://www.idref.fr/095348743 https://viaf.org/viaf/23268861 http://isni.org/isni/0000000043124960 Bruno Escoffier 45ad6b7432df4bb0628803bf27a7e2e3 upmc.fr brunoescoffier 5124 24013-5124 https://orcid.org/0000-0002-6477-8706 https://www.idref.fr/067352421 http://isni.org/isni/0000000358818668 https://viaf.org/viaf/211089377 http://www.researcherid.com/rid/CPG-4773-2022 http://www.researcherid.com/rid/http://www.researcherid.com/rid/CPG-4773-2022 Niklas Hahn 2900615-0 Michalis Xefteris 15139ac724bb73902c9978b1f3a2840f lip6.fr 1197213 2664175-1197213 https://orcid.org/0009-0006-2894-3029 https://www.idref.fr/284818240 Niklas Hahn a9c900504c005245b66f6b7d2a62eca3 ist.ac.at 2023-09-15 17:22:11 2025-07-23 03:19:25 2023-09-15 17:22:11 2023-07-31 contributor Niklas Hahn a9c900504c005245b66f6b7d2a62eca3 ist.ac.at CCSD hal-04208894 https://hal.sorbonne-universite.fr/hal-04208894 bampis:hal-04208894 <i>Algorithms and Data Structures Symposium (WADS)</i>, Jul 2023, Montreal, Canada. pp.65-78, <a target="_blank" href="https://dx.doi.org/10.1007/978-3-031-38906-1_5">&#x27E8;10.1007/978-3-031-38906-1_5&#x27E9;</a> Algorithms and Data Structures Symposium (WADS), Jul 2023, Montreal, Canada. pp.65-78, &#x27E8;10.1007/978-3-031-38906-1_5&#x27E9; CNRS - Centre national de la recherche scientifique Laboratoire d'Informatique de Paris 6 Sorbonne Université Sorbonne Université 01/01/2018 Faculté des Sciences de Sorbonne Université Sorbonne Université - Texte Intégral ANR Alliance Sorbonne Université Mathématiques + Informatique International No No Yes Yes Online TSP with Known Locations Evripidis Bampis 86302bba886873f656fe083cf63d42ea ibisc.univ-evry.fr 1284586 145111-1284586 https://orcid.org/0000-0002-4498-3040 https://www.idref.fr/095348743 https://viaf.org/viaf/23268861 http://isni.org/isni/0000000043124960 Bruno Escoffier 45ad6b7432df4bb0628803bf27a7e2e3 upmc.fr brunoescoffier 5124 24013-5124 https://orcid.org/0000-0002-6477-8706 https://www.idref.fr/067352421 http://isni.org/isni/0000000358818668 https://viaf.org/viaf/211089377 http://www.researcherid.com/rid/CPG-4773-2022 http://www.researcherid.com/rid/http://www.researcherid.com/rid/CPG-4773-2022 Niklas Hahn 2900615-0 Michalis Xefteris 15139ac724bb73902c9978b1f3a2840f lip6.fr 1197213 2664175-1197213 https://orcid.org/0009-0006-2894-3029 https://www.idref.fr/284818240 Algorithms and Data Structures Symposium (WADS) 2023-07-31 2023-08-02 Montreal Canada Springer Nature Switzerland Cham Lecture Notes in Computer Science 14079 65-78 2023-07-28 2210.14722 10.1007/978-3-031-38906-1_5 English Computer Science [cs] Conference papers Conference papers Conference papers

In this paper, we consider the Online Traveling Salesperson Problem (OLTSP) where the locations of the requests are known in advance, but not their arrival times. We study both the open variant, in which the algorithm is not required to return to the origin when all the requests are served, as well as the closed variant, in which the algorithm has to return to the origin after serving all the requests. Our aim is to measure the impact of the extra knowledge of the locations on the competitiveness of the problem. We present an online 3/2-competitive algorithm for the general case and a matching lower bound for both the open and the closed variant. Then, we focus on some interesting metric spaces (ring, star, semi-line), providing both lower bounds and polynomial time online algorithms for the problem.

 Recherche Opérationnelle RO 2018-01-01
13558292X 199712651U https://ror.org/05krcen59 LIP6 2018-01-01
4 Place JUSSIEU 75252 PARIS CEDEX 05
http://www.lip6.fr/ 221333754 https://ror.org/02en5vm52 Sorbonne Université SU 2018-01-01
21 rue de l’École de médecine - 75006 Paris
http://www.sorbonne-universite.fr/ 02636817X 0000000122597504 https://ror.org/02feahw73 Centre National de la Recherche Scientifique CNRS 1939-10-19
https://www.cnrs.fr/ ANR-19-CE48-0016 AlgoriDAM Théorie algorithmique de nouveaux modèles de données 2019