Approximation Algorithms for the Traveling Salesman Problem with Range Condition

DOI10.1051/ITA:2000113zbMATH Open0970.68196OpenAlexW2123771041MaRDI QIDQ4522112FDOQ4522112

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/

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

zbMATH Keywords

odd degree restricted graphs

Mathematics Subject Classification ID

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

Cites Work

• Faster scaling algorithms for general graph matching problems
• The Euclidean traveling salesman problem is NP-complete
• Title not available (Why is that?)
• The Traveling Salesman Problem with Distances One and Two
• Title not available (Why is that?)
• Title not available (Why is that?)
• Performance Guarantees for Approximation Algorithms Depending on Parametrized Triangle Inequalities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)