The Traveling Salesman Problem (TSP) is the task of finding a route through a given set of cities with shortest possible length. Many practical applications (VLSI design, etc.) can be modeled as a TSP. But, TSP is NP-hard, so the efficient approximation algorithms have been studied so far. In this paper, we show new approximation algorithms for TSP and the experimental results for these algorithms.
雑誌名
Research reports of the Faculty of Engineering, Mie University
巻
25
ページ
81 - 96
発行年
2000-12-27
ISSN
0385-6208
書誌レコードID
AA00816341
フォーマット
application/pdf
著者版フラグ
publisher
その他のタイトル
On the Approximation Algorithm for Traveling Salesman Problem
巡回セールスマン問題の近似アルゴリズムについて
AA008163410250009.PDF
(812.41KB)
