WEKO3
アイテム
非線形施設配置問題における貪欲法の遅延評価による高速化――複数施設が確率的に貢献する場合
https://ipsj.ixsq.nii.ac.jp/records/72664
https://ipsj.ixsq.nii.ac.jp/records/72664e5610f26-dde5-46e2-aeb1-18ab11ced10c
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-TOM0401002.pdf (1.2 MB)
|
Copyright (c) 2011 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Trans(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2011-01-26 | |||||||
| タイトル | ||||||||
| タイトル | 非線形施設配置問題における貪欲法の遅延評価による高速化――複数施設が確率的に貢献する場合 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Speed-up of Greedy Method by Lazy Evaluation on Nonlinear Facility Location Problem ― Case of Probabilistic Contribution by Multiple Facilities | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | オリジナル論文 | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 静岡県立大学 | ||||||||
| 著者所属 | ||||||||
| 静岡県立大学 | ||||||||
| 著者所属 | ||||||||
| 静岡県立大学 | ||||||||
| 著者所属 | ||||||||
| 静岡県立大学 | ||||||||
| 著者所属 | ||||||||
| 静岡県立大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Shizuoka | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Shizuoka | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Shizuoka | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Shizuoka | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Shizuoka | ||||||||
| 著者名 |
武藤, 伸明
× 武藤, 伸明
|
|||||||
| 著者名(英) |
Nobuaki, Mutoh
× Nobuaki, Mutoh
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 施設配置問題は，施設を開設するコストと利用者が施設を利用するコストの和を最小化する問題である．本論文では，利用コストに複数施設が確率的に貢献するタイプの施設配置問題を考える．その解法として，コストの総和を目的関数とした貪欲法，あるいは解品質の向上のため単位開設コストあたりのコストの総和の差分を評価関数とする貪欲法が考えられる．本論文では，これらの目的関数および評価関数の数理構造を分析し，これらの貪欲法に遅延評価と呼ばれる手法が導入可能なことを示す．また計算機実験によって，遅延評価の導入による高速化の効果を明らかにする． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We address the problem of locating a number of facilities requiring opening costs, so as to maximize the expected benefits of users in the setting that multiple facilities can contribute to users with some probabilities. In this paper, after showing that this location problem has a submodular property, we present two solution methods based on a greedy algorithm, and propose their speed-up method by incorporating a technique called lazy evaluation on the submodular problem. In our experiments using three real data sets, we show that the proposed method can stably produce desirable results. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AA11464803 | |||||||
| 書誌情報 |
情報処理学会論文誌数理モデル化と応用（TOM） 巻 4, 号 1, p. 1-10, 発行日 2011-01-26 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7780 | |||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
