betaFeedback

WorksComputer Science

Improved Approximation and Hardness Bounds for ββ-TSP

Abstract

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 P=NP\mathrm{P}=\mathrm{NP}, metric instances admit Christofides' 3/23/2-approximation, and fixed-dimensional Euclidean instances admit a PTAS. We study ββ-TSP, where the edge lengths satisfy ℓuw≤β(ℓuv+ℓvw)∀ u,v,w∈V pairwise distinct,β∈[12,1]. \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 11 at β=1/2β=1/2 to 3/23/2 as ββ approaches 11. We obtain a strictly better guarantee for every 1/2<β<11/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<β<11/2<β<1.

Paper details

vlnc:W_ky3pkxv2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…