DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.15

A (5/3+ε)-Approximation for Tricolored Non-Crossing Euclidean TSP

Authors: Júlia Baligács, Yann Disser, Andreas Emil Feldmann, and Anna Zych-Pawlewicz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

In the Tricolored Euclidean Traveling Salesperson problem, we are given k = 3 sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on "patching" for the case k = 1 and, recently, Dross et al. (2023) generalized this result to k = 2. Our contribution is a (5/3+ε)-approximation algorithm for k = 3 that further generalizes Arora’s approach. It is believed that patching is generally no longer possible for more than two tours. We circumvent this issue by either applying a conditional patching scheme for three tours or using an alternative approach based on a weighted solution for k = 2.

Cite as

Júlia Baligács, Yann Disser, Andreas Emil Feldmann, and Anna Zych-Pawlewicz. A (5/3+ε)-Approximation for Tricolored Non-Crossing Euclidean TSP. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.ESA.2024.15,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Feldmann, Andreas Emil and Zych-Pawlewicz, Anna},
  title =	{{A (5/3+\epsilon)-Approximation for Tricolored Non-Crossing Euclidean TSP}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.15},
  URN =		{urn:nbn:de:0030-drops-210862},
  doi =		{10.4230/LIPIcs.ESA.2024.15},
  annote =	{Keywords: Approximation Algorithms, geometric Network Optimization, Euclidean TSP, non-crossing Structures}
}

Document

DOI: 10.4230/LIPIcs.ESA.2023.11

Exploration of Graphs with Excluded Minors

Authors: Júlia Baligács, Yann Disser, Irene Heinrich, and Pascal Schweitzer

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g ≥ 1 and recovers the known tight bound for the planar case (g = 0).

Cite as

Júlia Baligács, Yann Disser, Irene Heinrich, and Pascal Schweitzer. Exploration of Graphs with Excluded Minors. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.ESA.2023.11,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Heinrich, Irene and Schweitzer, Pascal},
  title =	{{Exploration of Graphs with Excluded Minors}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.11},
  URN =		{urn:nbn:de:0030-drops-186644},
  doi =		{10.4230/LIPIcs.ESA.2023.11},
  annote =	{Keywords: online algorithms, competitive analysis, graph exploration, graph spanners, minor-free graphs, bounded genus graphs}
}

Search Results

Documents authored by Baligács, Júlia

A (5/3+ε)-Approximation for Tricolored Non-Crossing Euclidean TSP

Abstract

Cite as

Exploration of Graphs with Excluded Minors

Abstract

Cite as

Thanks for your feedback!

Could not send message