整数計画による点集合の最小凸分割の解法【JST・京大機械翻訳】

Sapucaia Allan; de Rezende Pedro J.; de Souza Cid C.

プレプリント

J-GLOBAL ID：202202206275896685 整理番号：22P0215648

整数計画による点集合の最小凸分割の解法【JST・京大機械翻訳】

Solving the Minimum Convex Partition of Point Sets with Integer Programming

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2020年12月06日プレプリントサーバーでの情報更新日： 2020年12月06日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

ある特性を満たすより小さな部分問題への問題の分割は,分割統治アルゴリズムの設計において,しばしば重要な構成要素である。位置に関連する質問のために,分割問題は,平面地図の細分化を見つけるので,幾何学的な項でモデル化できる,すなわち,ある条件に従う地理的領域,すなわち,いくつかの目的関数を最適化する。本論文では,最小凸分割問題(MCPP)として知られるこれらの幾何学的問題の1つを調べた。平面における点集合Pの凸状分割は,エッジがPの両端でセグメントであり,すべての内部面が空の凸多角形であるようなPの凸包の分割である。MCPPはNP困難問題であり,最小数の顔で凸状分割を見つけるのが一つの探索である。MCPPのための新しい多角形ベース整数計画定式化を提示し,これは以前に知られているエッジベースモデルよりも良い二重限界を導いた。さらに,プライムヒューリスティック,分岐ルールおよび価格決定アルゴリズムを導入した。これらの技術の組合せは,同一の計算資源に制約される間,以前に可能なように2倍多くのポイントでインスタンスを解決する能力をもたらす。この設計選択の影響を示すために包括的な実験的研究を提示した。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

図形・画像処理一般 , グラフ理論基礎

, , ,

前のページに戻る