CS Paper Radar

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

Jingyang Zhao, Trung Q. Duong, Een-Kee Hong, Hyundong Shin

cs.DS ·submitted 2026-11-04 12:12 UTC · v1

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.

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.88
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

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

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.72
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 $(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.72
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

Traveling Salesman Problem on Graphs with Proportional Independent Set

cs.DS math.CO ·2026-10-30 ·Ethan X. Fang, Shengtao Guo, Junwei Lu, Yuan Yao
similarity 0.71
Abstract · 13 pages, 2 figures

We give a deterministic algorithm for minimum-cost Hamiltonian cycle in undirected graphs with arbitrary real edge costs and an independent set of size at least $αn$, for any fixed $3/7<α\le1/2$. It runs in $O^*(γ(α)^n)$ time for an explicit constant $γ(α)<2$; for bipartite graphs, the bound is $O^*((1+2\sqrt2)^{n/2})\approx O^*(1.957^n)$. The algorithm is based on a restricted Held--Karp dynamic program. Its state enumeration uses structural properties of minimum-cost assignments arising from a regular triangulation of a product of simplices.

0.16

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.68
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 Asymmetric Multi-Path TSP

cs.DS ·2026-11-19 ·Manuel Christalla, Vera Traub
similarity 0.67
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 Approximations for Vehicle Routing with Nonuniform Speeds

cs.DS ·2026-10-08 ·Hong Li
similarity 0.67
Abstract · 21 pages, no figures

We study vehicle routing with vehicles of different speeds on a complete undirected graph whose vertex set consists of a depot and a set of clients, where the distances satisfy the triangle inequality. Each vehicle has a specified speed, and if the total length traveled by a vehicle of speed $s$ is $L$, its completion time is $L/s$. In the heterogeneous traveling salesman problem (HetTSP), each vehicle executes one tour starting and ending at the depot, and the tours collectively visit all clients. The objective is to minimize the maximum completion time among the vehicles. We give a $6$-approximation algorithm for HetTSP, improving the previous $90(1+δ)$-approximation for any fixed $δ>0$. We also consider two versions of the heterogeneous capacitated vehicle routing problem (HetCVRP). Each client has a demand, and the vehicles have identical capacities. A vehicle may execute several tours, each starting and ending at the depot, and reload at the depot between consecutive tours; the total demand delivered on each tour cannot exceed the vehicle capacity. In the split-delivery version of HetCVRP, the demand of a client may be divided among multiple visits, possibly by different vehicles. We give a $\frac92+2\sqrt3<7.965$-approximation algorithm for this problem. In the unsplit-delivery version of HetCVRP, the entire demand of each client must be delivered in a single visit. We give a $\frac{11}{2}+3\sqrt2<9.743$-approximation algorithm, improving the previous $450(1+δ)$-approximation for any fixed $δ>0$.

0.18