| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2013-09-03 10:10 An O(n log n) Algorithm for the Minimax Regret Sink Location Problem in Dynamic Path Networks with the Uniform Capacity ○Yuya Higashikawa（Kyoto Univ.）・Mordecai J. Golin（HKUST）・Naoki Katoh（Kyoto Univ.）  COMP2013-25 |
|
| 抄録 | （和） | 本論文では, 最大後悔値最小化を目的とする, 動的パスネットワーク上における施設配置問題を扱う. 動的パスネットワークは, 正の辺長と一様な辺容量をもつ無向パスによって構成される. 各頂点においてはサプライ（避難者）のインターバルが与えられており, 各頂点に対してインターバルを満たすような供給の割り当てをシナリオと呼ぶ. あるシナリオ$s$の下で1つの施設（避難所）の位置を$x$と決定したとき, シナリオ$s$における施設配置$x$のコストを, $s$の与えるネットワーク上のすべてのサプライが$x$への避難を完了するために必要な最小時間として定義する. このとき, $s$における$x$の後悔値を, $x$のコストから$s$における最適配置のコストを引いたものと定義する. さらに, $x$の最大後悔値を, $x$の後悔値のすべての可能なシナリオに対する最大値と定義するとき, 問題の目的は最大後悔値を最小化する施設配置を求めることである. 本論文では, 以上の問題に対して$O(n log n)$時間アルゴリズムを提案した. ここで$n$はネットワークの頂点数である. この結果は[6]によって提案されたアルゴリズムの計算時間を改善している. |
| （英） | This paper considers minimax regret 1-sink location problems in {it dynamic path networks}. In our model, a dynamic path network consists of an undirected path with positive edge lengths and uniform edge capacity, and the vertex supply which is nonnegative value is unknown but only the interval of supply is known. A particular assignment of supply to each vertex is called a {it scenario}. Under any scenario, the cost of a sink location is defined as the minimum time to complete evacuation for all supplies (evacuees), and the {it regret} of a sink location $x$ is defined as the cost of $x$ minus the cost of the optimal sink location. Then, the problem is to find a point as a sink such that the maximum regret for all possible scenarios is minimized. We present an $O(n log n)$ time algorithm for minimax regret 1-sink location problems in dynamic path networks with uniform capacity, where $n$ is the number of vertices in the network. This improves upon the existing time bound of $O(n log^2 n)$ by [6]. |
|
| キーワード | （和） | 最大後悔値最小化 / 施設配置 / 動的フロー / 避難計画 / / / / |
| （英） | minimax regret / sink location / dynamic flow / evacuation planning / / / / | |
| 文献情報 | 信学技報, vol. 113, no. 198, COMP2013-25, pp. 1-8, 2013年9月. | |
| 資料番号 | COMP2013-25 | |
| 発行日 | 2013-08-27 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2013-25 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2013-09-03 - 2013-09-03 |
| 開催地（和） | 鳥取環境大学 |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2013-09-COMP |
| 本文の言語 | 英語 |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | An O(n log n) Algorithm for the Minimax Regret Sink Location Problem in Dynamic Path Networks with the Uniform Capacity |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 最大後悔値最小化 / minimax regret |
| キーワード(2)（和/英） | 施設配置 / sink location |
| キーワード(3)（和/英） | 動的フロー / dynamic flow |
| キーワード(4)（和/英） | 避難計画 / evacuation planning |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 東川 雄哉 / Yuya Higashikawa / ヒガシカワ ユウヤ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | Mordecai J. Golin / Mordecai J. Golin / |
| 第2著者 所属（和/英） | The Hong Kong University of Science and Technology (略称： HKUST) The Hong Kong University of Science and Technology (略称： HKUST) |
| 第3著者 氏名（和/英/ヨミ） | 加藤 直樹 / Naoki Katoh / カトウ ナオキ |
| 第3著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第4著者 氏名（和/英/ヨミ） | / / |
| 第4著者 所属（和/英） | (略称： ) (略称： ) |
| 第5著者 氏名（和/英/ヨミ） | / / |
| 第5著者 所属（和/英） | (略称： ) (略称： ) |
| 第6著者 氏名（和/英/ヨミ） | / / |
| 第6著者 所属（和/英） | (略称： ) (略称： ) |
| 第7著者 氏名（和/英/ヨミ） | / / |
| 第7著者 所属（和/英） | (略称： ) (略称： ) |
| 第8著者 氏名（和/英/ヨミ） | / / |
| 第8著者 所属（和/英） | (略称： ) (略称： ) |
| 第9著者 氏名（和/英/ヨミ） | / / |
| 第9著者 所属（和/英） | (略称： ) (略称： ) |
| 第10著者 氏名（和/英/ヨミ） | / / |
| 第10著者 所属（和/英） | (略称： ) (略称： ) |
| 第11著者 氏名（和/英/ヨミ） | / / |
| 第11著者 所属（和/英） | (略称： ) (略称： ) |
| 第12著者 氏名（和/英/ヨミ） | / / |
| 第12著者 所属（和/英） | (略称： ) (略称： ) |
| 第13著者 氏名（和/英/ヨミ） | / / |
| 第13著者 所属（和/英） | (略称： ) (略称： ) |
| 第14著者 氏名（和/英/ヨミ） | / / |
| 第14著者 所属（和/英） | (略称： ) (略称： ) |
| 第15著者 氏名（和/英/ヨミ） | / / |
| 第15著者 所属（和/英） | (略称： ) (略称： ) |
| 第16著者 氏名（和/英/ヨミ） | / / |
| 第16著者 所属（和/英） | (略称： ) (略称： ) |
| 第17著者 氏名（和/英/ヨミ） | / / |
| 第17著者 所属（和/英） | (略称： ) (略称： ) |
| 第18著者 氏名（和/英/ヨミ） | / / |
| 第18著者 所属（和/英） | (略称： ) (略称： ) |
| 講演者 | 第1著者 |
| 発表日時 | 2013-09-03 10:10:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2013-25 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.198 |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2013-08-27 (COMP) |
[研究会発表申込システムのトップページに戻る]