平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
スポンサーリンク
概要
- 論文の詳細を見る
平面上に点集合Sが与えられた時、固定された原点とSの高々k点を通る巡回路をSのk巡回路と呼ぶ。我々の目的は、Sのすべての点をk巡回路の集合で被覆しその総長を最小化することである。kが定数のとき、この問題に対してHaimovichとRinnooy Kanによる多項式時間近似スキームが知られている。本稿では別の考え方に基づく多項式時間近似スキームを与える。この結果はdが定数である限りd次元空間における問題に拡張できる。対照的に、点集合が一般的な計量空間に置かれた場合にはこの問題はAPX完全であることを示す。
- 一般社団法人情報処理学会の論文
- 1996-09-13
著者
-
徳山 豪
東北大学大学院情報科学研究科
-
徳山 豪
東北大学情報科学研究科
-
浅野 哲夫
北陸先端科学技術大学院大学 情報科学研究科
-
加藤 直樹
神戸商科大学管理科学科
-
浅野 孝夫
中央大学理工学部情報工学科
-
徳山 豪
IBM東京基礎研究所
-
玉木 久夫
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.
-
浅野 哲夫
大阪電気通信大学
関連論文
- 画像切り出しに対するアルゴリズムの提案 (アルゴリズムと計算機科学の数理的基盤とその応用)
- センサーネットワークの位相情報の検知に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 複数のデジタル図形の最適切り出しについて
- 基本図形分割可能領域の最適切り出しアルゴリズム
- 非交差最小木の計算複雑度のパラメタ依存について
- Wireless Ad-Hocネットワークにおける干渉軽減法に関する研究
- 都市距離空間への新規高速道路の最適建設問題に対する擬凸最適化を用いた改良アルゴリズム
- ヨーロピアンアジアンオプションの効率的な価格付けの手法 : AMOアルゴリズムの実装と解析の改良
- 進化木のQuarted distanceの計算アルゴリズムの実装
- 多変数パラメトリック探索による最小値最大最適化問題の解法
- 最適ハイウェイ配置問題
- 2.高密度部分グラフの抽出 : その計算限界と打破(特定領域研究「新世代の計算限界-その解明と打破-」)
- 地形図からの最適ピラミッドの構成アルゴリズム
- 多値属性を用いた最適なデータセグメンテーションを生成するアルゴリズム
- ランダムアルゴリズムの話題から
- センサーネットワークの位相情報の検知に関する研究 (コンピュテーション)
- Geometric Problems on Ad-Hoc Network Design (Computational Geometry and Discrete Mathematics)
- D-022 動画に対するコメントを利用した自動Web検索システム(データベース,一般論文)
- A-003 アドホックネットワーク上でのランダム局所近傍を利用した幾何ルーティングアルゴリズムの設計と解析(モデル・アルゴリズム・プログラミング,一般論文)
- RA-006 リストページ自動分割問題の最適グラフ分割を用いた解法の提案と評価(モデル・アルゴリズム・プログラミング,査読付き論文)
- アドホックネットワーク上でのランダム局所近傍を利用した幾何ルーティングアルゴリズムの設計と解析
- メッシュネットワークにおけるジオメトリックルーティングに関する研究
- 数学的整合性を持つデジタル直線集合
- ディジタル星型領域とその応用
- D_036 Webデータの自動抽出とデータ変換(D分野:データベース)
- 関数近似における幾何学アルゴリズムの最近の進展 : データ解析への応用に向けて(新世代の計算限界-その解明と打破-招待解説論文)
- Web検索結果におけるクラスタリングアルゴリズムの研究
- アメリカン・アジアンオプションの価格の近似に対する計算幾何手法的アプローチ
- アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム(計算機科学の理論とその応用)
- ヨーロピアン・アジアンオプションの価格付けに関する近似的解法
- ディスクレパンシー基準によるディジタルハーフトーニング : 自動評価手法と最適化手法
- 実数列の大域的丸めの数え上げ
- 可変形状ラベリング問題に対するアルゴリズム
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- パラメトリックなポリマトロイドとその幾何学的応用
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 特別講演:デジタル平面の計算幾何学
- ユークリッド空間及びノルム空間における地帯図
- 長方形やタブローの同時配置における隅位置情報の効果
- 距離等分の存在
- 地図への高速ラベル貼りアルゴリズムの実装と評価
- A-12 左順序付き柔軟ラベリングの実装(画像,A.アルゴリズム・基礎)
- ゾーンダイアグラム : 存在性,一意性,アルゴリズム
- 中立地帯を持ったボロノイ図に関する考察
- 距離和最小化基準による点集合の折れ線近似
- ディジタルハーフトーニングに関連する組み合わせ問題と幾何問題
- Matrix Rounding under the L_p-Discrepancy Measure and Its Application to Digital Halftoning
- 実数行列のチェッカーボード型整数化について
- ディジタルハーフトーニング : ネットワークフローアルゴリズムによる最適化
- Digital Halftoning : Formulation as a Combinatorial Optimization Problem and Approximation Algorithms Based on Network Flow (Algorithm Engineering as a New Paradigm)
- 計算複雑度から見たディジタルハーフトーニング (新しいパラダイムとしてのアルゴリズム工学)
- クラス間分散最大区間を求めるアルゴリズムと多次元への拡張
- イメージ切り出しに関するアルゴリズム
- 電子マネーシステムにおける最適なオンラインアルゴリズム
- ヨーロッパ型及び貯蓄型アジアオプションの高精度かつ高速な価格計算
- 数値データからの直交凸領域結合ルール発見
- 領域及び区間分割を用いた決定木の作成 : 領域分割の有効性の検証
- データベースからの決定木構成における数理的問題
- データマイニングの最新動向 : 巨大データからの知識発見技術 (情報処理最前線)
- 最適区間問題と計算幾何学
- 距離$k$分割線と一般図形のゾーン図の存在と一意性について (理論計算機科学の深化と応用)
- Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図
- RA-006 基単調領域の非交差和領域の最適イメージ切り出しアルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- グラフに関する丸め問題:外平面グラフの場合
- グラフの準平衡彩色 : ディスクレパンシー条件による2色彩色
- センサーネットワークの位相情報の検知に関する研究
- D-026 ジャストインタイムウェブ広告におけるタクソノミ自動生成手法(データベース,一般論文)
- チェッカーボード丸めに関する考察と実装
- Image Recognition and Retrieval by Using Distance Information (Mathematical Foundations and Applications of Computer Science and Algorithms)
- タブローの最適配置問題 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 二部グラフの高濃度部分グラフ問題の近似アルゴリズムについて
- 二部グラフの高濃度部分グラフ問題の近似アルゴリズムについて
- 高次元ピラミッド構築問題とデータマイニングへの応用
- タブローの最適配置問題
- Image recognition and retrieval by using distance information (計算機科学とアルゴリズムの数理的基礎とその応用--RIMS研究集会報告集)
- パスカル三角形を用いたLow-Discrepancy Sequences構成法
- 良い『メモリ図』の生成
- 曲線のピーク削減アルゴリズムの考察と実装
- F-050 数値データベースに対するエキスパート付き決定木の構築(F.人工知能)
- LA-2 地形図からの最適ピラミッドの構成アルゴリズム(A. アルゴリズム・基礎)
- D-043 Web検索解析によるクラスタリング手法の研究(D.データベース)
- A Unified Scheme for Detecting Fundamental Curves in Binary Edge Images
- 曲線の最小Frechet距離近似に関するアルゴリズムの実装
- Quantum Algorithms for Intersection and Proximity Problems
- Quantum Computation in Computational Geometry
- 量子計算での幾何学データ処理
- パラメトリック最適化と計算幾何学
- MAXIMIN LOCATION OF CONVEX OBJECTS IN A POLYGON AND RELATED DYNAMIC VORONOI DIAGRAMS
- データベースからの知識発見に使われる計算幾何学 (特集 計算幾何の拡がり--情報科学・応用数理・数学にまたがる発展)
- J.E. Goodman, J. O'Rourke 編, Handbook of Discrete and Computational Geometry, CRC Press, 1997
- K-レベルとパラメトリック最小木の極値列挙について
- 3次元凹曲面族のk-レベルに対するロバシュの捕題とその応用
- 直線のアレンジメントの部分構成アルゴリズムと2色点集合の最適分割問題への応用
- Distance Trisector Curveに関する研究の誕生から発展までの経緯
- 最大重み領域を用いた画像切り出し
- データマイニングに使われる最適化の数理(最適化の数理)
- 第4巻第1号発行にあたって
- 計算幾何学 : 幾何学図形処理の手法とその応用
- 第6回ACM計算幾何学国際会議報告
- J.Bokowski, B.Sturmfels 著, "Computational Synthetic Geometry", Lecture notes in Mathematics 1355, Springer-Verlag, B5, 168p., 1989