betaFeedback

WorksComputer Science

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

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 NN 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 kk 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=2k=2. Whether the BTSP and the BTSPP admit constant-factor approximation algorithms for any fixed integer k>2k>2 has remained an open question. We resolve this question affirmatively. We show that both the BTSP and the BTSPP admit O(k)O(k)-approximation algorithms with running time NO(2kk!)N^{O(2^k k!)}. Moreover, for the BTSPP with k=2k=2, we propose an improved (α+2+ε)(α+2+\varepsilon)-approximation algorithm, where α<3/2−10−34α<3/2-10^{-34} is the best-known approximation ratio for the metric TSP, improving upon the previous ratio of 44

Paper details

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

views · 9

downloads · 0

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

  • Computer Science

AI tools

View statement
Looking for related papers…