Not all insertion methods yield constant approximate tours in the Euclidean plane
From MaRDI portal
Publication:1318697
DOI10.1016/0304-3975(94)90257-7zbMATH Open0802.90108OpenAlexW2041332016MaRDI QIDQ1318697FDOQ1318697
Authors: Vineet Bafna, Bala Kalyanasundaram, Kirk Pruhs 
Publication date: 5 April 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)90257-7
Recommendations
- Lower Bounds for Insertion Methods for TSP
- Touring polygons: an approximation algorithm
- Existence and computation of tours through imprecise points
- On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
- scientific article; zbMATH DE number 1559543
- Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
- Efficient algorithms for touring a sequence of convex polygons and related problems
- Approximation algorithms for geometrical distance problems that are not solvable exactly
- Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem
- On constant-weight TSP-tours
Cites Work
- The relative neighbourhood graph of a finite planar set
- Title not available (Why is that?)
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Dynamic Steiner Tree Problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower Bounds for Insertion Methods for TSP
- Title not available (Why is that?)
- Constructing Reliable Communication Networks of Small Weight Online
- Constructing competitive tours from local information
Cited In (8)
- The power of recourse for online MST and TSP
- Probabilistic analysis of optimization problems on sparse random shortest path metrics
- Distributed boundary coverage with a team of networked miniature robots using a robust market-based algorithm
- Lower Bounds for Insertion Methods for TSP
- Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem
- Constructing competitive tours from local information
- Insertion heuristics for central cycle problems
- Constructing competitive tours from local information
This page was built for publication: Not all insertion methods yield constant approximate tours in the Euclidean plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1318697)
