Approximating Traveling Salesman Problems Using a Bridge Lemma Article Swipe

MAKE IMPACT

Martin Böhm , Zachary Friggstad , Tobias Mömke , Joachim Spoerhase · YOU? · · 2024 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2405.12876

We give improved approximations for two metric Traveling Salesman Problem (TSP) variants. In Ordered TSP (OTSP) we are given a linear ordering on a subset of nodes $o_1, \ldots, o_k$. The TSP solution must have that $o_{i+1}$ is visited at some point after $o_i$ for each $1 \leq i < k$. This is the special case of Precedence-Constrained TSP ($PTSP$) in which the precedence constraints are given by a single chain on a subset of nodes. In $k$-Person TSP Path (k-TSPP), we are given pairs of nodes $(s_1,t_1), \ldots, (s_k,t_k)$. The goal is to find an $s_i$-$t_i$ path with minimum total cost such that every node is visited by at least one path. We obtain a $3/2 + e^{-1} < 1.878$ approximation for OTSP, the first improvement over a trivial $α+1$ approximation where $α$ is the current best TSP approximation. We also obtain a $1 + 2 \cdot e^{-1/2} < 2.214$ approximation for k-TSPP, the first improvement over a trivial $3$-approximation. These algorithms both use an adaptation of the Bridge Lemma that was initially used to obtain improved Steiner Tree approximations [Byrka et al., 2013]. Roughly speaking, our variant states that the cost of a cheapest forest rooted at a given set of terminal nodes will decrease by a substantial amount if we randomly sample a set of non-terminal nodes to also become terminals such provided each non-terminal has a constant probability of being sampled. We believe this view of the Bridge Lemma will find further use for improved vehicle routing approximations beyond this paper.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2405.12876

PDF

https://arxiv.org/pdf/2405.12876

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4398230519

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4398230519

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2405.12876

Digital Object Identifier

Title

Approximating Traveling Salesman Problems Using a Bridge Lemma

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2024

Year of publication

Publication date

2024-05-21

Full publication date if available

Authors

Martin Böhm, Zachary Friggstad, Tobias Mömke, Joachim Spoerhase

List of authors in order

Landing page

https://arxiv.org/abs/2405.12876

Publisher landing page

PDF URL

https://arxiv.org/pdf/2405.12876

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2405.12876

Direct OA link when available

Concepts

Lemma (botany), Bridge (graph theory), Mathematics, Combinatorics, Computer science, Biology, Botany, Anatomy, Poaceae

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload