| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-01-25 09:30 枝コストに制限を加えたk-Canadian Traveller Problemの競合比解析 ○福田剛士・宮崎修一・岡部寿男（京大）  COMP2009-39 |
|
| 抄録 | （和） | オンライン問題の一つに$k$-Canadian Traveller Problem($k$-CTP)がある． $k$-CTPとは, 枝に重みの付いたグラフ$G=(V,E)$上の与えられた頂点$s$から$t$までの最短経路問題である． オンラインアルゴリズムは前もってグラフの構造と全ての枝のコストを知っている． しかし, グラフ上で高々$k$個の枝が封鎖されており, 枝が封鎖されているか否かはその枝に隣接する頂点に辿り着いた時に初めて分かる． Westphalは任意のグラフに対して, 競合比が$2k+1$になることを示した． 本稿では, 枝コストに制限をかけた場合の$k$-CTPの競合比解析を行う． 具体的には, 完全グラフに対し, 枝コストが全て1の場合, 枝コストが三角不等式を満たす場合に対して, それぞれ競合比が$\frac{k+1}{2}$, $k$になることを示す (グラフの連結性を保証するために, 全封鎖数$k$は$|V|-2$以下とする)． |
| （英） | The $k$-Canadian Traveller Problem ($k$-CTP) is one of the online problems. In this problem, we are given an undirected edge-weighted graph $G=(V,E)$, a source vertex $s$, and a destination vertex $t$, and our purpose is to traverse $G$ from $s$ to $t$. An online algorithm knows the topology of $G$ and the weight of each edge in advance. However, at most $k$ edges of $G$ are blocked and the algorithm cannot go through these edges. Initially, the algorithm does not know which edges are blocked; when it reaches either endpoint of a blocked edge, it first learns that this edge is blocked. For this problem, Westphal gave a deterministic (2$k$+1)-competitive algorithm, and proved that there is no better algorithm. In this paper, we restrict the graph class to obtain a better competitive ratio. Specifically, we consider the case that (i) edge weights are uniform (i.e., all the weights are 1), and (ii) edge weights satisfy the triangle inequality, on complete graphs. (We also assume that $k≦|V|-2$ in order to guarantee the connectivity of the input graphs.) In both cases, we give optimal online algorithms whose competitive ratios are ($k$+1)/2 and $k$, respectively. |
|
| キーワード | （和） | オンラインアルゴリズム / 競合比解析 / 最短経路問題 / / / / / |
| （英） | online algorithm / competitive analysis / the shortest path problem / / / / / | |
| 文献情報 | 信学技報, vol. 109, no. 391, COMP2009-39, pp. 1-8, 2010年1月. | |
| 資料番号 | COMP2009-39 | |
| 発行日 | 2010-01-18 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2009-39 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2010-01-25 - 2010-01-25 |
| 開催地（和） | 九州大学西新プラザ |
| 開催地（英） | Nishijin Plaza, Kyushu University |
| テーマ（和） | 情報処理学会アルゴリズム研究会との連続開催 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2010-01-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 枝コストに制限を加えたk-Canadian Traveller Problemの競合比解析 |
| サブタイトル（和） | |
| タイトル（英） | Competitive Analysis of the k-Canadian Traveller Problem for Graphs with Restricted Edge Weights |
| サブタイトル（英） | |
| キーワード(1)（和/英） | オンラインアルゴリズム / online algorithm |
| キーワード(2)（和/英） | 競合比解析 / competitive analysis |
| キーワード(3)（和/英） | 最短経路問題 / the shortest path problem |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 福田 剛士 / Takeshi Fukuda / フクダ タケシ |
| 第1著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 宮崎 修一 / Shuichi Miyazaki / ミヤザキ シュウイチ |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 岡部 寿男 / Yasuo Okabe / オカベ ヤスオ |
| 第3著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-01-25 09:30:00 |
| 発表時間 | 35分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2009-39 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | no.391 |
| ページ範囲 | pp.1-8 |
| ページ数 | 8 |
| 発行日 | 2010-01-18 (COMP) |
[研究会発表申込システムのトップページに戻る]