文献

J-GLOBAL ID：201902223182919888   整理番号：19A0010732

媒介変数表示される重みに対する最大後悔最小化1-センター問題

Minimax Regret 1-Center Problems with Parametric Weights

著者 (5件)： 大勝章平 (関西学院大 理工) ,  加藤直樹 (関西学院大 理工) ,  照山順一 (兵庫県大 社会情報科学) ,  東川雄哉 (兵庫県大 経営) ,  巳波弘佳 (関西学院大 理工)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 118  号： 216(COMP2018 9-20)(Web)  ページ： 29-33 (WEB ONLY)  発行年： 2018年09月11日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本稿では,ロバスト最適化の一枠組みである最大後悔最小化モデルを用いて,重み付き無向グラフにおける1-センター問題を扱う。入力グラフは,各頂点の重みを時刻に対して正数を返す関数として,また各辺の長さを正数として持つ。時刻tにおいて,施設配置点xに対する頂点vの重み付き距離を,グラフにおけるx-v間の最短距離とvの重みの積として定義するとき,施設配置点xの配置コストは,xに対する各頂点の最大重み付き距離として定義される。また,時刻tにおける施設配置点xの後悔は,tにおけるxの配置コストと最適配置コストの差として定義される。このとき,全時刻にわたる後悔の最大値を最小化する施設配置点の発見が目的となる。本稿では,グラフがパス・木の場合に対する多項式時間アルゴリズムを提案する。(著者抄録)

シソーラス用語： アルゴリズム ,  無向グラフ ,  *配置問題 ,  防災計画 ,  *防護施設
準シソーラス用語： 多項式時間アルゴリズム ,  *施設配置問題 ,  避難計画 ,  *避難施設 ,  最適配置

分類 (1件)： 数値計算  (JE02000J)

引用文献 (20件)：

• M. J. Atallah, “Some Dynamic Computational Geometry Problems,” Computers & Mathematics with Applications, 11(12), pp. 1171-1181, 1985.
• I. Averbakh and O. Berman, “Minimax Regret p-Center Location on a Network with Demand Uncertainty,” Location Science, 5(4), pp. 247-254, 1997.
• I. Averbakh and O. Berman, “Minmax Regret Median Location on a Network under Uncertainty,” INFORMS Journal on Computing, 12(2), pp. 104-110, 2000.
• I. Averbakh and O. Berman, “An Improved Algorithm for the Minmax Regret Median Problem on a Tree,” Networks, 41(2), pp. 97-103, 2003.
• B. K. Bhattacharya, T. Kameda and Z. Song, “A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network,” Algorithmica, 70(1), pp. 2-21, 2014.

タイトルに関連する用語 (4件)： 媒介変数 ,  後悔 ,  最小化 ,  センター