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

参考文献10件

書誌事項

タイトル別名
  • Some Results for Cluster Traveling Salesperson Problem

この論文をさがす

説明

本稿では, クラスタ巡回セールスマン問題と呼ばれる(略して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.

収録刊行物

参考文献 (10)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1573105977191078016
  • NII論文ID
    110003191275
  • NII書誌ID
    AN10013152
  • 本文言語コード
    en
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ