経路最適化問題の近似アルゴリズム : 幾何学的/非幾何学的場合の対比
スポンサーリンク
概要
- 論文の詳細を見る
NP困難な組合せ最適化問題に対する近似解を求める方法とその困難さの研究がここ数年で急速な進展をみせている。特に近似困難性の理論 [PY91, FGLSS91, ALMSS92] がこの分野を大いに刺激し、多くの肯定的および否定的な研究結果が生み出された [CK]。肯定的な結果では昨年Aroraによる平面上の巡回セールスマン問題に対する多項式時間近似スキーム [Aro96] が注目を浴びた。これは、都市が平面上に配置され巡回路の長さをユークリッド距離で計る場合、任意の定数ε>0に対してε近似多項式時間アルゴリズム (最適解の (1+ε) 倍以内の解を都市数nの多項式時間で求める) が存在することを示したものであり、長年の未解決問題に解答を与えた。この結果は次の二つの否定的結果と対比するとさらに興味深い。第一に、巡回セールスマン問題を正確に解く問題は平面上でユークリッド距離を用いる場合に限定してもNP困難であることが古くから知られている [Pap77, GGJ76]。第二に、巡回路の長さが三角不等式を満たす一般の距離で計られる場合には多項式時間近似スキームは存在しない (P=NPでない限り) [PY93]。つまり、NP困難性の壁を越えることが問題の幾何学的性質の利用と近似問題への緩和を同時に行なうことによって初めて可能だったわけである。これは、次々といろいろな問題に対する近似困難性の結果が生み出されるなかで、一筋の光明を与え研究のひとつの方向を示唆している : 幾何学的性質は近似解を求めるのに役に立つ ; これは他の問題に対してもそうだろうか?もちろん、一般的問題が困難な時にやさしく解ける特殊な場合を探求するというのは常套の方法論であり、幾何学的性質の利用はその一例にすぎない。しかしながら、巡回セールスマン問題という基本的な問題に対して、ユークリッド平面への限定が実際に近似問題をやさしくするかどうかが知られていなかった、それが肯定的に解決されたことが希望を与えてくれる。Aroraは彼の方法の応用として、巡回セールスマン問題以外にも様々な幾何的最適化問題に対して多項式時間近似スキームを与えている。ほかにも、例えば集合被覆問題のように、一般の問題はε近似が困難だが能率よく近似できるような幾何学的特殊例が知られているようようなものがある。講演者らは、巡回セールスマン問題の一般化であるk巡回路被覆問題 (3節参照) のある部分クラスについて、同様の幾何学的/非幾何学的な場合の困難性の対比が成り立つことを示した [AKTT96a, AKTT96b]。本講演では、Aroraの巡回セールスマン問題に対する結果と講演者らのk巡回路被覆問題に対する結果に焦点を絞って解説する。
- 社団法人電子情報通信学会の論文
- 1997-03-06
著者
-
玉木 久夫
IBM東京基礎研究所
-
玉木 久夫
明治大学理工学部情報科学科
-
Tamaki Hisao
The School Of Science And Technology Meiji University
-
Tamaki Hisao
Department Of Computer Science Meiji University
-
Hisao Tamaki
Department Of Computer Science Meiji University.
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 点集合の距離重複度列のノルムと最大部分集合問題
- 密な部分グラフ問題の貪欲解法
- 放物線のアレンジメントの組合せ複雑度について
- 平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて
- 頂点彩色問題に対する列生成法アプローチの高速化
- テストパターンの静的圧縮における厳密解と貧欲解の比較(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 平面ユークリッドTSPの分割統治法ヒューリスティツクス
- 平面グラフの分枝幅決定アルゴリズムの効率的実装
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- 合成数のAKS witnessに関する実験的研究
- 小さな碁盤における囲碁の厳密解アルゴリズム
- TD-1-12 アルゴリズムデモ発見的動的計画法 : 巡回セールスマン問題を例として
- ハイパーキューブ上の順列の同形を反復しない網羅的生成
- 平面巡回セールスマン問題に対するアローラの近似アルゴリズムの効率的実装
- Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm)
- 障害物との交差数が少ない全域木
- パラメトリックなポリマトロイドとその幾何学的応用
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 巡回カメラマン問題とその自動光学的検査への応用
- 教育を目的としたC言語ソース管理APIの作成とその応用(e-learning/一般)
- JavaのeラーニングのためのEclipseプラグインの開発(e-learning/一般)
- 極小横断列挙のメモリ効率の良いアルゴリズム
- 2H-7 耐故障トーラス構成の一方式とシミュレーションによる評価
- Voronoi Diagrams with Respect to Criteria on Vision Information
- 単一根有向グラフと対称変換に基づいた囲碁の棋譜管理・閲覧システムの開発(セッション(1) : ゲーム情報学(1))
- 巡回セールスマン問題の近似アルゴリズム:天才アローラによる20年ぶりの急進展(近似アルゴリズムに関する最近の話題)
- 経路最適化問題の近似アルゴリズム : 幾何学的/非幾何学的場合の対比
- ハイパーキューブ上の単距離置換のルーティング
- 組合せ的解析における確率的手法
- Graph Orientation Problems for Multiple st-Reachability
- k-cyclic Orientations of Graphs
- グラフの自動描画における交差を考慮した巨大近傍探索
- Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths
- Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
- Approximation Algorithms for Geometric Optimization Problems(Special Issue on Algorithm Engineering : Surveys)
- Computing directed pathwidth in O(1.89n) time
- A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
- A Linear Edge Kernel for Two-Layer Crossing Minimization
- Search space reduction through commitments in pathwidth computation: an experimental study