CS Paper Radar

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

Jingyang Zhao, Yuxi Liu, Mingyu Xiao

cs.DS ·submitted 2026-09-17 01:01 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Constant-Factor Approximations for the Biased Traveling Salesman Problem and Its Path Variant

cs.DS ·2026-11-05 ·Jingyang Zhao, Jason William Setiawan, Uman Khalid, Chaoning Zhang, Een-Kee Hong +1 more
similarity 0.75
Abstract

The metric traveling salesman problem (TSP) is a fundamental problem in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices, where edge costs satisfy the triangle inequality. The biased TSP (BTSP) is a natural generalization of the metric TSP, in which the vertex set is partitioned into $k$ subsets: edge costs satisfy the triangle inequality within each subset, while edges crossing the subsets may violate the triangle inequality by a certain bias factor. This model captures scenarios in which distances are metric only locally but may be distorted across different regions or types of vertices. In this paper, we study approximation algorithms for the BTSP and its path variant, the biased traveling salesman path problem (BTSPP), which asks for a minimum-cost Hamiltonian path. Previously, constant-factor approximation algorithms were known only for the case $k=2$. Whether the BTSP and the BTSPP admit constant-factor approximation algorithms for any fixed integer $k>2$ has remained an open question. We resolve this question affirmatively. We show that both the BTSP and the BTSPP admit $O(k)$-approximation algorithms with running time $N^{O(2^k k!)}$. Moreover, for the BTSPP with $k=2$, we propose an improved $(α+2+\varepsilon)$-approximation algorithm, where $α<3/2-10^{-34}$ is the best-known approximation ratio for the metric TSP, improving upon the previous ratio of $4$

0.15

Polynomial $(2α+\varepsilon)$- and Quadratic $4$-Approximation Algorithms for the Biased Traveling Salesman Problem in Bipartitioned Networks

cs.DS ·2026-11-04 ·Jingyang Zhao, Trung Q. Duong, Een-Kee Hong, Hyundong Shin
similarity 0.72
Abstract

The traveling salesman problem (TSP) is one of the fundamental problems in combinatorial optimization that asks for a minimum-cost Hamiltonian cycle in a complete undirected graph with $N$ vertices. For the metric TSP, where edge costs satisfy the triangle inequality, a long line of work has produced constant-factor approximation algorithms, culminating in the best-known approximation ratio $α<3/2-10^{-36}$. The biased TSP (BTSP) generalizes the metric TSP to bipartitioned networks: the vertex set is partitioned into two subsets, edge costs satisfy the triangle inequality within each subset, while edges crossing the partition may violate it by a certain bias factor. This model captures heterogeneous routing scenarios in which distances are metric only locally but may be distorted across different regions or vertex types. Previously, the only known result for the BTSP was a $7/2$-approximation algorithm with running time $O(N^3)$. In this paper, we present two new approximation algorithms that significantly improve the state of the art. The first achieves an approximation ratio of $2α+\varepsilon$ (strictly less than $3$) in polynomial time $N^{O(1)}$ for any constant $\varepsilon>0$, where the exponent grows at least linearly with $1/\varepsilon$. The second achieves a $4$-approximation in only $O(N^2)$ running time, reducing the previous cubic-time bound by a full polynomial factor. These advances directly support emerging networked systems---including multi-tier 6G architectures and hybrid quantum-classical networks---where cross-region transitions incur biased and non-metric overheads.

0.25

Approximation Algorithms for Asymmetric Multi-Path TSP

cs.DS ·2026-11-19 ·Manuel Christalla, Vera Traub
similarity 0.71
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.

0.11

Improved Approximation for Unsplittable Capacitated Vehicle Routing Using Quota Trees

cs.DS ·2026-10-20 ·Zhenyu Wang
similarity 0.70
Abstract

In the Unsplittable Capacitated Vehicle Routing Problem (UCVRP), we are given a set $V$ of $n$ clients with normalized demands $d_v \in (0,1]$, a depot $r$, a unit vehicle capacity, and symmetric metric travel costs $c$ on $V \cup \{r\}$. We seek a collection of routes of minimum total cost that start and end at $r$, serve each client's entire demand on a single route, and respect the unit capacity constraint $\sum_{v \in V(R)} d_v \le 1$ on every route $R$, where $V(R)$ denotes the clients served by $R$. UCVRP generalizes the metric traveling salesman problem (TSP) and is therefore NP-hard. Capacity constraints add a packing difficulty: when all clients are colocated away from the depot, minimizing the route cost is equivalent to minimizing the number of bins in bin packing. Consequently, UCVRP admits no polynomial-time approximation ratio below $3/2$ unless $\textbf{P=NP}$ (Grandoni, Mathieu, and Zhou, 2023). The classical $3.5$-approximation has been improved; Zhao and Xiao recently obtained a $(2+\ln 2+\varepsilon)$-approximation. In this paper, we give a deterministic polynomial algorithm with approximation ratio $5/2$ for general capacity and arbitrary positive demands. Our algorithm uses local search to select routes through one client with large demand and clients with small demands. It constructs candidate routes using endpoint quota trees after rounding demands and creating vertex copies. We replace selected routes using sets of two to four clients and a squared-weight local search, keeping their client sets disjoint. The remaining clients are served by partitioning a tour constructed using weighted graphic matroid parity. We also give a deterministic polynomial $5/2$-approximation algorithm for the undirected capacitated arc routing problem (CARP) with arbitrary positive edge demands.

0.16

Reducing Asymmetric Path TSP to Asymmetric TSP

cs.DS ·2026-11-16 ·Hong Li
similarity 0.69
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

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.69
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 PTAS for Euclidean Capacitated Vehicle Routing

cs.DS ·2026-11-13 ·Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi, Kinter Ren, Mohammad R. Salavatipour
top venuehot direction similarity 0.69
Abstract

In the Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, we are given an $n$-node graph $G=(V,E)$ with metric edges costs $c(e)$, a depot $r\in V$, and an integer vehicle capacity $Q$. The goal is to find a minimum-cost collection of tours, each containing the depot and visiting at most other $Q$ nodes, such that the tours cover all the nodes. In this paper we focus on the Euclidean CVRP problem, where the nodes represent points on $\mathbb{R}^2$, and the edge costs are the respective Euclidean distances. Euclidean CVRP generalizes the classical NP-hard Euclidean TSP problem (the special case with $Q=n-1$), that admits a PTAS [Arora FOCS'96/Mitchell SODA'96]. A long-standing open problem has been generalizing the latter PTAS to Euclidean CVRP. A polynomial-time $(2+ε)$-approximation for this problem follows from the PTAS for Euclidean TSP and the tour-partitioning technique for CVRP [Haimovich, Kan Math. OR'85]. This was the best known until a recent improvement of the approximation factor to slightly below 2 [Friggstad, Grandoni, Mousavi SODA'26]. There have been a series of papers presenting improved QPTASs by Das and Mathieu [SODA'10] (time $n^{\log^{O(1/ε)}n}$), Jayaprakash and Salavatipour [SODA'22] (time $n^{O_ε(\log^6 n)}$), and recently Sitters [ArXiV'25] (time $n^{O_ε(\log\log n)}$). In this paper, we solve the mentioned long-standing open problem by presenting a PTAS for Euclidean CVRP.

0.46

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