The approximation ratio of the greedy algorithm for the metric traveling salesman problem
From MaRDI portal
Publication:1785355
DOI10.1016/j.orl.2015.02.009zbMath1408.90247arXiv1412.7366OpenAlexW2055574289MaRDI QIDQ1785355
Judith Brecklinghaus, Stefan Hougardy
Publication date: 28 September 2018
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1412.7366
Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Uses Software
Cites Work
- Unnamed Item
- On the nearest neighbor rule for the metric traveling salesman problem
- Worst-case analysis of two travelling salesman heuristics
- The traveling salesman. Computational solutions for RSP applications
- On the nearest neighbor rule for the traveling salesman problem
- Reducibility among Combinatorial Problems