巡回セールスマン問題に対する近似の下界
スポンサーリンク
概要
- 論文の詳細を見る
任意の2点間の枝の重みに関して三角不等式が成り立つようなグラフ上の巡回セールスマン問題は, 代表的な組合せ最適化問題である.本稿では, その特殊な場合として, 任意の2点間の枝の重みが"1"または"2"に制限された巡回セールスマン問題(1, 2)-TSPについて考察する.実際, (1, 2)-TSPはNP完全であるので, その最適解(全ての点を一度ずつ通る最短閉路)を求めることはNP困難である.そこで(1, 2)-TSPを最小化問題MIN-(1, 2)-TSPとして定式化し, その近似解(全ての点を一度ずつ通る閉路)を求めることを考える.しかしMIN-(1, 2)-TSPはAPX完全であり, MIN-(1, 2)-TSPに関して, 非自明な近似の下界が存在する.最近Engebretsenは, 任意のε>0に対して-(1)無向MIN-(1, 2)-TSPを5381 / 5380-ε以内で近似するのはNP困難;(2)有向MIN-(1, 2)-TSPを2805 / 2804-ε以内で近似するのはNP困難-であることを示した.本稿ではこれらを改良し, 任意のε>0に対して-(Corollary 4.4)無向MIN-(1, 2)-TSPを1027 / 1026-ε以内で近似するのはNP困難;(Corollary 4.6)有向MIN-(1, 2)-TSPを535 / 534-ε以内で近似するのはNP困難-であることを示すとともに, 任意のε>0に対して, 最短超系列問題を2983 / 2982-ε以内で近似するのはNP困難(Corollary 5.3)であることを示す.
- 社団法人電子情報通信学会の論文
- 2000-03-22
著者
関連論文
- 1-C-3 数値計算解 : CRR市場上の最適多数回行使可能型アメリカン・ラシアン・アジアン・オプション(金融工学(1))
- キャンパス共通認証認可システムの構築と運用(セキュアでサステイナブルなインターネットアーキテクチャ論文)
- メルボルンでの8か月
- [チュートリアル講演]最小値独立置換族に関する最近の成果
- 最小値独立置換族に関する最近の成果
- 有限幾何を用いた線形サイズ4-制限最小値独立置換族の構成
- 近似的k-対独立置換族の構成
- k-制限最小値独立置換族,その他k-wise独立性のサンプルサイズ下界
- 置換族とその独立性の解析
- A Characterization of Min-Wise Independent Permutations Families (Models of Computation and Algorithms)
- 最適な最小値独立置換族の構成
- A Polynomial Time Sampling Algorithm for an Optimal Family of Min-Wise Independent Permutations (Models of Computation and Algorithms)
- 無効化とタイムアウトを考慮したLRUキャッシュの解析
- 簡便なハッシュ関数族の構成法
- 大学内の業務・システムと連携するキャンパス共通認証認可システムの構築と運用
- 言語に依存した安全なビット・コミットメント
- ゼロ知識証明モデルと計算量理論 (<小特集>ゼロ知識証明とその応用)
- Simulating Fair Dice with a Small Set of Rationally Biased Coins
- 無線LANにおけるセキュリティ技術の動向
- ビデオ配信スケジューリングの競合比の解析
- 自己検査器及び自己修正器の関係について
- On checkers, Self-Testers, and Self-Debuggers
- B-7-48 零知識証明を用いた分散個人認証システム
- 有限体上のアルゴリズムと多倍長・剰余演算の高速演算方 ( 数論アルゴリズムとその応用)
- ε-近似k-制限最小値独立置換族のサイズの下界
- 重み付き乱択最適選好マッチング
- フェイステル変換を用いた近似的k-対ランダム置換族の構成
- 最小値独立置換族と3点独立置換族
- 商品価格設定問題に対する近似アルゴリズム
- 決定性QoS問題の競合比の下界について
- A-7-10 プライバシーを考慮した情報獲得の最近の動向
- プライバシーを考慮した情報獲得プロトコルの通信量の下界
- 巡回セールスマン問題に対する近似の下界
- 凸型資本投資問題に対するオンラインアルゴリズムの設計と解析
- 1-B-4 FIFOキャッシュアルゴリズムの流体解析(待ち行列(1))
- 修正された選択離散対数問題の難しさについて
- 2011年度冬のLAシンポジウム Greedy Algorithms for Multi-Queue Buffer Management with Class Segregation (アルゴリズムと計算理論の新展開 : RIMS研究集会報告集)
- 線形符号の最大重みに対する近似アルゴリズム
- プライバシーを考慮した効果的な情報獲得
- RSA暗号の安全性に基づくID-NIKSの安全性について
- 非線形符号の半径及び被覆半径に対する近似アルゴリズム
- 非線形符号の半径及び被覆半径に対する近似アルゴリズム
- 非線形符号の半径及び被覆半径に対する近似アルゴリズム
- 統計的及び完全な知識の複雑さについて
- Crypto報告