CS Paper Radar

Approximation Algorithms for Asymmetric Multi-Path TSP

Manuel Christalla, Vera Traub

cs.DS ·submitted 2026-11-19 14:37 UTC · v1

Abstract

Asymmetric Multi-Path TSP is the generalization of the Asymmetric Traveling Salesperson Problem where we are looking for $k$ walks, each with prescribed start $s_i$ and prescribed end $t_i$, such that every vertex is visited by at least one of the walks. The objective is to minimize the total length of all walks. In general, it is NP-hard to find any approximation for this problem in polynomial time (even if the approximation factor is allowed to depend on the number of vertices). We show that one can obtain an $O(k)$-approximation in time $n^{O(k)}$, answering an open question by Friggstad [2013]. For the special case where all tour start vertices $s_i$ are identical and all end vertices $t_i$ are identical, we obtain an $O(k)$-approximation in polynomial time, as well as an $(O(\frac{1}ε), 1+ε)$-bicriteria approximation. For the multi-depot setting, where $s_i =t_i$ for all $i$, we obtain a constant-factor approximation in polynomial time. Finally, our results imply improved constant-factor approximation algorithms for Asymmetric Regret-Bounded Vehicle Routing and unit-weight Path ATSP.

Closest papers

Nearest neighbours by meaning across the whole index.

Reducing Asymmetric Path TSP to Asymmetric TSP

cs.DS ·2026-11-16 ·Hong Li
similarity 0.74
Abstract · 20 pages, 3 figures

In the Asymmetric Traveling Salesman Problem (Asymmetric TSP), we are given distances between $n$ vertices that satisfy the triangle inequality but need not be symmetric, and we seek a shortest tour through all vertices. In its path version, Asymmetric Path TSP, two vertices $s$ and $t$ are prescribed, and we seek a shortest path from $s$ to $t$ through all vertices. Both problems are equivalent to their versions with arbitrary nonnegative edge costs on a directed graph, in which vertices may be visited more than once. We show that for all constants $α\ge1$ and $\varepsilon>0$, any $α$-approximation algorithm for Asymmetric TSP yields an $(α+\varepsilon)$-approximation algorithm for Asymmetric Path TSP. The best previous reduction of this kind, due to Feige and Singh, yields an $α(2+\varepsilon)$-approximation algorithm. Our result answers an open question of Traub and Vygen. Consequently, every constant-factor approximation guarantee for Asymmetric TSP carries over to Asymmetric Path TSP up to an arbitrarily small additive error.

0.11

A polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in fixed dimension

cs.DS math.CO ·2026-11-11 ·Daniel Skachkov, Yuriy Dorn
similarity 0.73
Abstract

In the Traveling Salesman Problem, a route must visit all customers and return to its starting point while minimizing its total length. The Minimum Latency Problem, also known as the Traveling Repairman Problem, instead minimizes the sum of the times at which customers are first visited. We give a deterministic polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in every fixed dimension, with arbitrary nonnegative customer weights. Our proof restricts the form of a solution in three steps, each with a controlled increase in cost. First, a decomposition based on Sitters' method assigns customers to phases that start and end at the root. Second, within each phase, we divide the route into a constant number of blocks and charge each customer at the end of its assigned block. The resulting objective is a nonnegative linear combination of block lengths. Third, we add an auxiliary dimension and use a fixed Minkowski norm to close each block path into a tour. Arora's closed-tour estimate then gives paths that cross the boundaries of a common dissection only at designated portals and a bounded number of times per face. A dynamic program optimizes the restricted objective, and projecting its paths back to the original space gives the final route. Rounding weights and coordinates keeps the state space polynomial.

0.30

A $(1+1/\sqrt{2})$-Approximation for the Multiple-Depot Traveling Salesman Problem

cs.DS ·2026-09-17 ·Jingyang Zhao, Yuxi Liu, Mingyu Xiao
similarity 0.71
Abstract

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost tour covering all clients in a metric graph. The metric multiple-depot TSP (MD-TSP) is a natural extension, where the graph contains depots and clients, and the objective is to compute a minimum-cost set of tours covering all clients, with each tour starting and ending at the same depot. When the number of depots is part of the input, an adaptation of the Christofides--Serdyukov heuristic yields an approximation ratio of $2$. In this paper, we introduce a $(1+1/\sqrt{2})$-approximation algorithm. Like the Christofides--Serdyukov heuristic, our algorithm first computes a rooted spanning forest (RSF), then a matching to correct its odd degrees, and finally obtains a solution by shortcutting. However, instead of using a minimum-cost RSF, we construct an RSF by a primal-dual algorithm for a natural cut relaxation. The algorithm grows rootless components and the component containing all depots at different rates, adding an edge when its dual constraint becomes tight. Vertex labels record the times at which clients first become connected to a depot. The two-speed growth provides a joint bound on the forest cost and two label-dependent terms that also arise in bounding the parity-correction cost. Balancing the coefficients of these two terms by setting both to $\sqrt{2}-1$ yields the claimed approximation ratio.

0.14

Improved Approximation and Hardness Bounds for $β$-TSP

cs.DS cs.CCmath.OC ·2026-11-06 ·Paul Liu, Jack Spalding-Jamieson, Da Wei Zheng
similarity 0.70
Abstract · 12 pages

The traveling salesman problem (TSP) asks for a minimum-length Hamiltonian cycle in a complete weighted graph. Its approximability depends on the edge lengths: unrestricted instances admit no constant-factor approximation unless $\mathrm{P}=\mathrm{NP}$, metric instances admit Christofides' $3/2$-approximation, and fixed-dimensional Euclidean instances admit a PTAS. We study $β$-TSP, where the edge lengths satisfy $ \ell_{uw}\leqβ(\ell_{uv}+\ell_{vw}) \qquad \forall\,u,v,w\in V\ \text{pairwise distinct}, \quad β\in\left[\tfrac{1}{2},1\right]. $ The condition arises naturally in various settings, for example, when metric travel times are combined with positive service times at the vertices. The previous best approximation algorithm, due to Böckenhauer et al., ranges from $1$ at $β=1/2$ to $3/2$ as $β$ approaches $1$. We obtain a strictly better guarantee for every $1/2<β<1$ by combining two simple constructions whose guarantees counterbalance each other. We also improve the best known approximation hardness bound for every $1/2<β<1$.

0.23

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

cs.DS ·2026-10-13 ·Vikrant Ashvinkumar
similarity 0.69
Abstract · More detailed AI statement. Polished exposition and fixed typos

In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. Ashvinkumar, Bernstein, and Karczmarz (SODA 2025) gave the first randomized bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm on directed graphs running in sub-$mn$ time, answering a problem posed by Bernstein (SODA 2012). We substantially improve this on two fronts, supplying a deterministic bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm running in near-linear time. Our approach straightforwardly generalizes to more than two resources. For $k$ resources, a deterministic $(1+\varepsilon_1,\ldots,1+\varepsilon_k)$-approximate algorithm running in near-linear time is possible, with $\varepsilon_1=\ldots=\varepsilon_k=\varepsilon$.

0.20

A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth

cs.DS cs.CC ·2026-09-24 ·DongYun Byun, Akira Matsubayashi
theory similarity 0.69
Abstract · 22 pages, 1 figure. Presented in IPEC 2026

The $k$ vertex-disjoint paths problem asks whether, given a graph $G$ and $k$ pairs of vertices $(s_1,t_1)$, \ldots, $(s_k,t_k)$, $G$ has $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all $1\leq i\leq k$. If $G$ is undirected, then this problem is NP-complete, but there exist FPT algorithms parameterized by $k$.Since these algorithms involve an extremely large function on $k$, algorithms for restricted graphs have also been investigated. In particular, a $2^{2tw\log tw+O(tw)}\cdot n$ time algorithm for undirected graphs with $n$ vertices and treewidth $tw$ is proposed by Scheffler (Technical Report 396, TU Berlin, '94), and it is proved by Lokshtanov, Marx, and Saurabh (SIAM J. Comput. '18) that, under the ETH, there exists no $2^{o(pw\log pw)}\cdot n^{O(1)}$ time algorithm for either directed or undirected graphs with pathwidth $pw$ and for $k=Ω(pw^4)$. It has not been known whether the lower bound also holds for a smaller $k$. In this paper, we prove that, for both the directed and undirected cases, there is an algorithm faster than Lokshtanov et al.'s lower bound for $k=tw^{o(1)}$ by proposing a $2^{O((tw+k)\log k)}\cdot n$ time algorithm. Besides, we prove a lower bound that, under the SETH, there exists no $(2-ε)^{pw\log pw}\cdot n^{O(1)}$ time algorithm for directed graphs and for a general $k$. This lower bound is tight because, with slight modifications, Scheffler's algorithm runs in $2^{pw\log pw+O(pw)}\cdot n$ time also for directed graphs.

0.26

Approximation Algorithms for Graphic Multi-Depot TSP and Graphic Multi-Path TSP

cs.DS ·2026-10-12 ·Niklas Dahlmeier, Raoul Luqué, Philipp Pabst, Laura Vargas Koch
similarity 0.68
Abstract · 22 pages, 3 figures, 1 table, 1 linear program, 2 algorithms

We give improved approximation algorithms for two graphic TSP variants. First, we consider Multi-Depot TSP on graphic instances. In this variant, we are given an undirected graph with a set of depot vertices, and we are tasked with finding an Eulerian multi-edge set that connects each non-depot vertex to at least one depot. For this problem, Deppert, Kaul and Mnich (ESA 2023) presented a 3/2-approximation algorithm with running time exponential in the number of depots. We improve this result to a fully polynomial 3/2-approximation. Our algorithm is a variant of the classic Christofides-Serdyukov algorithm with an improved and simple analysis. On subcubic instances, we improve the approximation guarantee to 4/3 using the technique of removable pairings introduced by Mömke and Svensson (J. ACM 2016). We use a removable pairing to construct a set of disjoint cycles that can be completed to a cheap feasible solution. Second, we consider the Graphic Multi-Path TSP, which was previously considered by Alimi, Dahlmeier, Mömke, Pabst and Vargas Koch (SOSA 2026) who give a 2-approximation for this problem. Additionally, the authors present a reduction that shows that any better-than-two approximation for Graphic Multi-Depot TSP immediately leads to an improvement for Graphic Multi-Path TSP. We give an improved algorithm and analysis that yield an approximation guarantee of 1.9304.

0.17

Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP

cs.DS ·2026-10-13 ·Sharareh Alipour, Ali Nowzari
similarity 0.68
Abstract

We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, $(1,2)$-TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm estimates the optimum cost of an $n$-vertex $(1,2)$-TSP instance from above within factor $2-\cstar+\eps=1.413184\ldots+\eps$, with high probability, in $n^{2-Ω_\eps(1)}$ time, where $\cstar=2(\sec1-\tan1)$. This improves the $3/2+\eps$ factor of direct matching estimation in this subquadratic regime~\cite{BhattacharyaKissSaranurak2023} and of the faster near-linear estimator~\cite{BehnezhadEtAl2024}. A single random vertex order defines an implicit bipartite graph whose matchings project to path covers. An alternating-permutation analysis shows that its expected maximum matching size is at least $\cstar$ times the optimum path-cover size. On long paths, even the best of polynomially many uniform orders retains only a $\cstar+o(1)$ fraction with high probability. In semi-streaming, we construct deterministic $(5/7-\eps)$-approximate unweighted path covers and $(9/7+\eps+5/(7n))$-approximate $(1,2)$-TSP tours, improving the respective $2/3-\eps$ and $4/3+\eps+1/n$ guarantees in~\cite{AlipourFarokhnejadMoemke2025}. For nonnegative weights, we obtain $2/3-\eps$ for path cover and Max-TSP, improving the earlier asymptotic $7/12-\eps$ Max-TSP bound. These algorithms use $\poly(1/\eps)$ passes independent of $n$ and $O(n\log(n/\eps)\poly(1/\eps))$ words. We compute two approximate matchings separated by edge deletion. A cycle-compensation lemma accounts for the weight removed when breaking their cycles. For unweighted graphs, a third approximate matching on a simple auxiliary graph with at most $2n$ vertices chooses component connections; a Tutte--Berge count proves the stronger bound.

0.25