ある拡張された巡回セールスマン問題について

10 References
  • BODLAENDER Hans L.
    Department of Computer Science, Utrecht University
  • YAMAZAKI Koichi
    Department of Computer Science and Information Mathematics, The University of Electro-Communications

Bibliographic Information

Other Title
  • Some Results for Cluster Traveling Salesperson Problem

Search this article

Description

本稿では, クラスタ巡回セールスマン問題と呼ばれる(略してCTSP), ある拡張された巡回セールスマン問題について考える. CTSPとは, 入力としてグラフG=(V,E)とVの分割V_1,…,V_kが与えられ, 各クラスタV_i対し, 少なくともV_iに属する1つの頂点を含む, 最小コストの巡回路を見つける問題である. 本稿では, 三角不等式を満たすCTSPに対する近似解を求めることは, 少なくとも最小セットカバーに対する近似解をもとめることよりも難しいことを示す. また, クラスタの数がkのとき, CTSPがO(2^<3k>・|V|^3)時間で解けることを示す.
In this paper, we consider a generalizion on the Traveling Salesperson Problem, called the Cluster Traveling Salesperson Problem (abbreviated CTSP). In CTSP, we are given a graph G=(V,E) and a partition of V: V_i,…,V_k (the 'clusters'); the goal is to find an optimum (i.e. shortest) tour which visits at least one city in each cluster. We will show that CTSP with triangle inequality is at least as hard to approximate as Minimum Set Cover. We also give an algorithm that solves k-CSTP in O(2^<3k>・|V|^3) time, where k denotes the number of clusters.

Journal

References(10)*help

See more

Keywords

Details 詳細情報について

  • CRID
    1573105977191078016
  • NII Article ID
    110003191275
  • NII Book ID
    AN10013152
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top