Approximation Algorithms for the Traveling Salesman Problem with Range Condition

DOI10.1051/ITA:2000113MaRDI QIDQ4522112zbMATH OpenOpenAlexFDO

Authors D. Arun Kumar, C. Pandu Rangan

Publication date 19 December 2000

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2000__34_3_173_0/, https://eudml.org/doc/92631

zbMATH Keywords

odd degree restricted graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Approximation algorithms (68W25)

Recommendations

• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• scientific article; zbMATH DE number 4095236
• scientific article; zbMATH DE number 1507218
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• The Traveling Salesman Problem with Distances One and Two

Cites work

• scientific article; zbMATH DE number 2185604 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1489999 (Why is no real title available?)
• scientific article; zbMATH DE number 1500530 (Why is no real title available?)
• scientific article; zbMATH DE number 1408349 (Why is no real title available?)
• scientific article; zbMATH DE number 3409134 (Why is no real title available?)
• Faster scaling algorithms for general graph matching problems
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• The Euclidean traveling salesman problem is NP-complete
• The Traveling Salesman Problem with Distances One and Two

Cited in

(1)

• An improved upper bound for the TSP in cubic 3-edge-connected graphs

This page was built for publication: Approximation Algorithms for the Traveling Salesman Problem with Range Condition

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