arXiv preprint ·
Approximating Prize-Collecting TSP below 1.556
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The prize-collecting traveling salesperson problem is a variant of the metric traveling salesperson problem in which vertices may be left unvisited by paying their associated penalties. The objective is to minimize the length of the tour plus the total penalty of the unvisited vertices. Blauth, Klein, and Nägele gave the previously best-known LP-relative $1.599$-approximation. We show that a simpler version of their algorithm, obtained by omitting the splitting-off preprocessing before the tree decomposition, has an LP-relative approximation ratio of $1.555761$. The improvement comes entirely from a new analysis of the parity-correction step: a simple analysis already gives $1.56$, and the stated factor follows from a numerical parameter search with exact verification.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Dimensional Ultra-Log-Concave Distributions
Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint
Byzantine Causal Reliable Broadcast (BCRB) with Constant-Size Message Metadata
Improved Algorithms for the Remote Point Problem
On Deterministically Computing Total Variation Distance via Zonotope Compression
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.