WEKO3
アイテム
Online TSP in a Simple Polygon
https://ipsj.ixsq.nii.ac.jp/records/80977
https://ipsj.ixsq.nii.ac.jp/records/80977d4825c77-2801-45d3-8e1d-16097c49199d
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL12139010.pdf (183.6 kB)
|
Copyright (c) 2012 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2012-03-07 | |||||||
| タイトル | ||||||||
| タイトル | Online TSP in a Simple Polygon | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Online TSP in a Simple Polygon | |||||||
| 言語 | ||||||||
| 言語 | eng | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | ショートトーク | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| Department of Architecture and Architectural Engineering, Kyoto University | ||||||||
| 著者所属 | ||||||||
| Department of Architecture and Architectural Engineering, Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Architecture and Architectural Engineering, Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Architecture and Architectural Engineering, Kyoto University | ||||||||
| 著者名 |
Yuya, Higashikawa
× Yuya, Higashikawa
|
|||||||
| 著者名(英) |
Yuya, Higashikawa
× Yuya, Higashikawa
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We consider an online traveling salesman problem in a simple polygon where starting from a point in the interior of a simple polygon, the searcher is required to explore a simple polygon to visit its all vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm. | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We consider an online traveling salesman problem in a simple polygon where starting from a point in the interior of a simple polygon, the searcher is required to explore a simple polygon to visit its all vertices and finally return to the initial position as quickly as possible. The information of the polygon is given online. As the exploration proceeds, the searcher gains more information of the polygon. We give a 1.219-competitive algorithm for this problem. We also study the case of a rectilinear simple polygon, and give a 1.167-competitive algorithm. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2012-AL-139, 号 10, p. 1-8, 発行日 2012-03-07 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
