The traveling salesman problem for lines and rays in the plane

DOI10.1142/S1793830912500449zbMATH Open1259.68236arXiv1204.5828MaRDI QIDQ4903631FDOQ4903631

Authors: Adrian Dumitrescu 

Publication date: 24 January 2013

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

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$.

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

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

zbMATH Keywords

linear programmingapproximation algorithmlinesraystraveling salesman problem with neighborhoodsminimum-perimeter rectangle

Mathematics Subject Classification ID

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

Cites Work

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