𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The n-line traveling salesman problem

✍ Scribed by Günter Rote

Publisher
John Wiley and Sons
Year
1992
Tongue
English
Weight
780 KB
Volume
22
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

The special case of the Euclidean traveling salesman problem, where the n given points lie on a small number (N) of parallel lines in the plane, is solved by a dynamic programming approach in time nN, for fixed N, i.e., in polynomial time. This extends a result of Cutler (1980) for three lines. Such problems arise, for example, in the fabrication of printed circuit boards, where the distance traveled by a laser that drills holes in certain places of the board should be minimized. The parallelity condition can be relaxed to point sets that lie on N "almost parallel" line segments. We give a characterization of the allowed segment configurations by a set of forbidden subconfigurations.

📜 SIMILAR VOLUMES

Efficient special case algorithms for th
Efficient special case algorithms for the n-line planar traveling salesman problem
✍ M. Cutler 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 482 KB

## Abstract The traveling salesman problem, path, or cycle is NP‐complete. All known exact solutions to this problem are exponential. In the __N‐line planar__ traveling salesman problem the points are on __N__ lines in the plane. In this paper, simple and efficient low‐degree polynomial solutions a