The traveling salesman problem for lines and rays in the plane

DOI10.1142/S1793830912500449MaRDI QIDQ4903631zbMATH OpenFDO

Authors Adrian Dumitrescu

Publication date 24 January 2013

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.5828

zbMATH Keywords

linear programmingapproximation algorithmlinesraystraveling salesman problem with neighborhoodsminimum-perimeter rectangle

Mathematics Subject Classification ID

Linear programming (90C05) Approximation algorithms (68W25)

Abstract: In the Euclidean TSP with neighborhoods (TSPN), we are given a collection of $n$ regions (neighborhoods) and we seek a shortest tour that visits each region. In the path variant, we seek a shortest path that visits each region. We present several linear-time approximation algorithms with improved ratios for these problems for two cases of neighborhoods that are (infinite) lines, and respectively, (half-infinite) rays. Along the way we derive a tight bound on the minimum perimeter of a rectangle enclosing an open curve of length $L$.

Recommendations

• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for TSP with neighborhoods in the plane
• The traveling salesman problem for lines, balls, and planes
• The traveling salesman problem for lines, balls and planes
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane

Cites work

• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation algorithms for the Geometric Covering Salesman Problem
• CORRIGENDUM TO "AN INCREMENTAL ALGORITHM FOR CONSTRUCTING SHORTEST WATCHMAN ROUTES"
• Fast computation of shortest watchman routes in simple polygons
• Finding the shortest watchman route in a simple polygon
• Linear Programming in Linear Time When the Dimension Is Fixed
• MINIMUM POLYGON TRANSVERSALS OF LINE SEGMENTS
• Minimum-perimeter intersecting polygons
• The traveling salesmanpProblem for lines in the plane

Cited in

(7)

• A fresh look at the traveling salesman problem with a center
• The traveling salesman problem on grids with forbidden neighborhoods
• The touring rays and related problems
• Polynomial-time algorithms for the touring rays and related problems
• The traveling salesman problem for lines, balls and planes
• The traveling salesmanpProblem for lines in the plane
• The Convex-hull-and-k-line Travelling Salesman Problem

This page was built for publication: The traveling salesman problem for lines and rays in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903631)