非線形施設配置問題における貪欲法の遅延評価による高速化-複数施設が確率的に貢献する場合-

• Item type: SIG Technical Reports(1)
• 公開日: 2010-05-14
• タイトル: 非線形施設配置問題における貪欲法の遅延評価による高速化-複数施設が確率的に貢献する場合-
• タイトル / 言語: en
• タイトル: Speed-up of Greedy Method by Lazy Evaluation on Nonlinear Facility Location Problem - Case of Probabilistic Contribution by Multiple Facilities -
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属: 静岡県立大学
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者所属(英): en
• 著者所属(英): University of Shizuoka
• 著者名: 武藤, 伸明; 斉藤, 和巳; 池田, 哲夫; 永田, 大; 伏見, 卓恭
• 著者名(英): Nobuaki, Mutoh; Kazumi, Saito; Tetsuo, Ikeda; Dai, Nagata; Takayasu, Fushimi
• 論文抄録 / 内容記述タイプ: 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
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 研究報告数理モデル化と問題解決（MPS）; 巻 2010-MPS-78, 号 4, p. 1-9, 発行日 2010-05-14
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会