Name
Abstract | ||
|---|---|---|
We consider the following maximum scatter traveling salesperson
problem (TSP): given an edge-weighted complete graph ${\cal
G}=(S,E)$, find a Hamiltonian path or cycle such that the length of a
shortest edge is maximized. In other words, the goal is to
have each point far away (most “scattered”) from the points that
are visited just before or just after it in the path/cycle. This is
also referred to as the max-min 1-neighbor TSP. More generally,
in the max-min m-neighbor TSP problem, the goal is to maximize
the minimum distance between any point and all of its
”m-neighbors” along the path/cycle. An m-neighbor of p
is a point that is at most m points away from p in the path/cycle.
These problems are closely related to the bottleneck TSP, and are
motivated by applications in manufacturing (e.g., sequencing of rivet
operations) and medical imaging.
In this paper we give O(n)-time approximation algorithms for
the max-min 2-neighbor TSP with the triangle inequality. We achieve an
approximation factor of 12 for the path version, and a factor of 18
for the cycle version of the problem, improving the previous best
factors of 32 and 64, respectively, for all cases of
n. Moreover, we present an O(mn)-time algorithm that
achieves a constant approximation factor of 16 for the path
version of the max-min m-neighbor TSP with the triangle inequality
when n = (m+1)k or when n = (m + 1)k + m, where $m \in
(2,n)$ is part of the input. This significantly improves the
previous best approximation factor of $4\cdot 8^{\lceil m/2
\rceil}$, from exponential in m to a small
constant. |
Year | DOI | Venue |
|---|---|---|
2005 | https://doi.org/10.1007/s00453-004-1124-z | Algorithmica |
Keywords | Field | DocType |
Traveling salesperson problem (TSP),Maximum scatter TSP,Bottleneck TSP,Hamiltonian cycle/path,Approximation algorithms,Matching,Optimization | Bottleneck,Approximation algorithm,Complete graph,Discrete mathematics,Combinatorics,Exponential function,Hamiltonian path,Travelling salesman problem,Triangle inequality,Mathematics | Journal |
Volume | Issue | ISSN |
41 | 4 | 0178-4617 |
Citations | PageRank | References |
1 | 0.36 | 4 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yi-jen Chiang | 1 | 503 | 38.21 |