| 講演名 | 2020-03-01 避難者数が媒介変数に依存する最大後悔最小化1-シンク配置問題 戸國 友貴(関西学院大), 加藤 直樹(兵庫県立大), 照山 順一(兵庫県立大), 東川 雄哉(兵庫県立大), 藤江 哲也(兵庫県立大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では単一の媒介変数により重みづけられた動的パスネットワーク上での最大後悔最小化1シンク配置問題を取り扱う．動的パスネットワークはパス状の無向グラフから構成され，グラフの各辺は正の長さと容量を，各頂点は単一媒介変数によって正の値をとる関数として重みを持つ．施設配置点$x$と媒介変数$t$に対して，$t$における$x$の配置コストはすべての避難者の$x$への避難時間の合計と定義する. $t$における$x$の後悔は，$t$における$x$の配置コストと最適配置コストの差により定義される. このとき，媒介変数の取り得るすべての値に対する後悔の最大値を最小化する施設配置点$x^{*}$の発見が目的となる．本稿では，この問題に対する初の多項式時間アルゴリズムを提案する． |
| 抄録(英) | This paper addresses the minmax regret 1-sink problem in dynamic path networks with parametric weights. A dynamic path network consists of an undirected path with positive edge lengths and edge capacities, and vertex weights given as positive functions in one parameter. For a sink location $x$ and a parameter value $t$, the location cost of $x$ under $t$ is defined as the sum of evacuation time to $x$ for all the evacuees under $t$. The regret of $x$ under $t$ is defined as the difference of the location cost of $x$ under $t$ from the optimal location cost under $t$. Our aim is to find a sink location $x^{*}$ which minimizes the maximum regret of $x$ over any possible $t$. In this paper, we present the first polynomial time algorithm for the problem. |
| キーワード(和) | 最大後悔最小化 / 施設配置問題 / 多項式時間アルゴリズム |
| キーワード(英) | minimax regret / facility location problem / polynomial time algorithm |
| 資料番号 | COMP2019-51 |
| 発行日 | 2020-02-23 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2020/3/1(から1日開催) |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 大舘 陽太(熊本大) / 玉置 卓(兵庫県立大) |
| 幹事氏名（英） | Yota Otachi(Kumamoto Univ) / Suguru Tamaki(Univ. of Hyogo) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 避難者数が媒介変数に依存する最大後悔最小化1-シンク配置問題 |
| サブタイトル（和） | |
| タイトル（英） | Minmax regret 1-sink problem with parametric weights |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 最大後悔最小化 / minimax regret |
| キーワード(2)（和/英） | 施設配置問題 / facility location problem |
| キーワード(3)（和/英） | 多項式時間アルゴリズム / polynomial time algorithm |
| 第 1 著者 氏名（和/英） | 戸國 友貴 / Yuki Tokuni |
| 第 1 著者 所属（和/英） | 関西学院大学(略称：関西学院大) Kwansei Gakuin University(略称：Kwansei Gakuin Univ.) |
| 第 2 著者 氏名（和/英） | 加藤 直樹 / Noaki Katoh |
| 第 2 著者 所属（和/英） | 兵庫県立大学(略称：兵庫県立大) University of Hyogo(略称：Univ. of Hyogo) |
| 第 3 著者 氏名（和/英） | 照山 順一 / Junichi Teruyama |
| 第 3 著者 所属（和/英） | 兵庫県立大学(略称：兵庫県立大) University of Hyogo(略称：Univ. of Hyogo) |
| 第 4 著者 氏名（和/英） | 東川 雄哉 / Yuya Higashikawa |
| 第 4 著者 所属（和/英） | 兵庫県立大学(略称：兵庫県立大) University of Hyogo(略称：Univ. of Hyogo) |
| 第 5 著者 氏名（和/英） | 藤江 哲也 / Tetsuya Fujie |
| 第 5 著者 所属（和/英） | 兵庫県立大学(略称：兵庫県立大) University of Hyogo(略称：Univ. of Hyogo) |
| 発表年月日 | 2020-03-01 |
| 資料番号 | COMP2019-51 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | COMP-433 |
| ページ範囲 | pp.35-41(COMP), |
| ページ数 | 7 |
| 発行日 | 2020-02-23 (COMP) |