著者

坂上 知英 吉澤 慎 太田 義勝 大山口 通夫 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.