このアイテムのアクセス数: 160
このアイテムのファイル:
| ファイル | 記述 | サイズ | フォーマット | |
|---|---|---|---|---|
| IPSJ-Z82-7L-01.pdf | 1.05 MB | Adobe PDF | 見る/開く |
| タイトル: | 直線上の2サーバーオンラインマッチング問題に対する貪欲アルゴリズムの競合比解析 |
| 著者: | 佐竹, 誠  宮崎, 修一 |
| 著者名の別形: | Satake, Makoto Miyazaki, Shuichi |
| 発行日: | 20-Feb-2020 |
| 出版者: | 情報処理学会 |
| 誌名: | 第82回情報処理学会全国大会 |
| 巻: | 2020 |
| 号: | 1 |
| 開始ページ: | 251 |
| 終了ページ: | 252 |
| 抄録: | 直線上のオンライン二部マッチング問題(Online Matching on a Line; OML)とは、事前に与えられたサーバー集合とオンライン形式で与えられるリクエスト集合に対してマッチング間の距離の和を最小化する問題である。現在OMLの競合比は上下限に大きな開きがある。そこで本論文では、OMLに制限を加えたモデルでより良い競合比を示すことを目的として、サーバーの位置が2箇所であるようなモデルを考察する。このモデルに対して貪欲アルゴリズムが競合比3を達成し、かつ任意の決定性アルゴリズムが3以上の競合比を持つことを示す。 |
| 著作権等: | ここに掲載した著作物の利用に関する注意: 本著作物の著作権は情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。 |
| URI: | http://hdl.handle.net/2433/254178 |
| 関連リンク: | http://id.nii.ac.jp/1001/00204987/ |
| 出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。