著者
坂上 知英 吉澤 慎 太田 義勝 大山口 通夫 SAKAGAMI Tomohide YOSHIZAWA Makoto OHTA Yoshikatsu OYAMAGUCHI Michio
出版者
Faculty of Engineering, Mie University
雑誌
Research reports of the Faculty of Engineering, Mie University (ISSN:03856208)
巻号頁・発行日
vol.25, pp.81-96, 2000-12-27

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.