講演抄録/キーワード |
講演名 |
2018-09-18 13:25
媒介変数表示される重みに対する最大後悔最小化1-センター問題 ○大勝章平・加藤直樹(関西学院大)・照山順一・東川雄哉(兵庫県立大)・巳波弘佳(関西学院大) COMP2018-13 |
抄録 |
(和) |
本稿では,ロバスト最適化の一枠組みである最大後悔最小化モデルを用いて,重み付き無向グラフにおけ る 1-センター問題を扱う.入力グラフは,各頂点の重みを時刻に対して正数を返す関数として,また各辺の長さを正 数として持つ.時刻 t において,施設配置点 x に対する頂点 v の重み付き距離を,グラフにおける x-v 間の最短距離 と v の重みの積として定義するとき,施設配置点 x の配置コストは,x に対する各頂点の最大重み付き距離として定 義される.また,時刻 t における施設配置点 x の後悔は,t における x の配置コストと最適配置コストの差として定義 される.このとき,全時刻にわたる後悔の最大値を最小化する施設配置点の発見が目的となる.本稿では,グラフが パス・木の場合に対する多項式時間アルゴリズムを提案する. |
(英) |
In this paper, based on the minimax regret model which is an approach for the robust optimization, we consider 1-center problems in weighted and undirected graphs. In an input graph, the weight of a vertex is given as a positive function in time and the length of an edge is given as a positive value. At time t, the weighted distance of v w.r.t. x is defined as the product of the shortest distance from v to x and the weight of v, and the location cost of x is defined as the maximum weighted distance w.r.t. x. The regret of x at time t is defined as the value subtracted the optimal location cost at t from the location cost of x at t. Our aim is to find the location which minimizes the maximum regret over time. We present polynomial time algorithms for the problems on paths and trees. |
キーワード |
(和) |
最大後悔最小化 / 施設配置問題 / 多項式時間アルゴリズム / / / / / |
(英) |
minimax regret / facility location problem / polynomial time algorithm / / / / / |
文献情報 |
信学技報, vol. 118, no. 216, COMP2018-13, pp. 29-33, 2018年9月. |
資料番号 |
COMP2018-13 |
発行日 |
2018-09-11 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2018-13 |