割り当て問題に対するランダムアルゴリズムの実験的検証
スポンサーリンク
概要
- 論文の詳細を見る
n人の人員をkヶ所にコストが最小となるように割り当てる問題を考える.まず問題を幾何学的に定式化することによりn>klogkのときに従来のものよりも速く解を求めるアルゴリズム(O(k^2nlogn)時間)を構成し,ランダム化の手法を用いてさらなる高速化をはかる(O(kn+k^<2.5>n^<0.5>log^<1.5>n)時間).次に計算機実験によって,ランダム化の効果とアルゴリズムのふるまいについて検証する.
- 1994-07-22
著者
関連論文
- 多値属性を用いた最適なデータセグメンテーションを生成するアルゴリズム
- 幾何学アルゴリズムとその応用
- ランダムアルゴリズムの話題から
- 割り当て問題に対するランダムアルゴリズムの実験的検証
- 点集合の距離重複度列のノルムと最大部分集合問題
- 密な部分グラフ問題の貪欲解法
- 放物線のアレンジメントの組合せ複雑度について
- 割り当て問題に対するランダマイズド・アルゴリズムの実験的検証
- 線分族と三角形族の中での直交探索
- Kリンク最短パス問題と行列探索
- 三角形族の中での直交探索
- 単体内の点集合の分割について(LP新解法)
- パラメトリックなポリマトロイドとその幾何学的応用
- クラス間分散最大区間を求めるアルゴリズムと多次元への拡張
- イメージ切り出しに関するアルゴリズム
- 電子マネーシステムにおける最適なオンラインアルゴリズム
- 数値データからの直交凸領域結合ルール発見
- 領域及び区間分割を用いた決定木の作成 : 領域分割の有効性の検証
- データマイニングの最新動向 : 巨大データからの知識発見技術 (情報処理最前線)
- 最適区間問題と計算幾何学
- 平行移動する複数の点集合または線分集合に対するVoronoi図の複数さと文字配置への応用
- Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図
- 点集合を分散の総和が最小となるようにk個のクラスターに分割するアルゴリズム
- ヒッチコック型輸送問題の新算法
- A Unified Scheme for Detecting Fundamental Curves in Binary Edge Images
- 直線のアレンジメントの部分構成アルゴリズムと2色点集合の最適分割問題への応用