WEKO3
アイテム
オンライン全域木の平均コンペティティブ比について
https://ipsj.ixsq.nii.ac.jp/records/32320
https://ipsj.ixsq.nii.ac.jp/records/32320f727ec87-f02b-440f-a8b9-f8725b1feda0
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL95048009.pdf (308.5 kB)
|
Copyright (c) 1995 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1995-11-17 | |||||||
| タイトル | ||||||||
| タイトル | オンライン全域木の平均コンペティティブ比について | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Average Competitive Ratios of On - Line Spanning Trees | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 群馬大学工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 群馬大学工学部情報工学科 | ||||||||
| 著者所属 | ||||||||
| 群馬大学工学部情報工学科 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Gunma University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Gunma University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Computer Science Gunma University | ||||||||
| 著者名 |
鮑豊
× 鮑豊
|
|||||||
| 著者名(英) |
Feng, Bao
× Feng, Bao
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 本論文は、ユークリッド平面上の同じ分布点からなるオンライン全域木の平均コンペティティブ比について論じる。どのようなオンラインアルゴリズムでもそのオンライン全域木の平均コンペティティブ比が1/8ln n ?1/2以上になるようなn個の点の分布を示す。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We study the average competitive ratio of on-line spanning trees with the same distribution of points in the Euclidean plane. We show a distribution of n points such that the average competitive ratio of on-line spanning trees by any on-line algorithm cannot be less than 1/8ln n -1/2. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1995, 号 109(1995-AL-048), p. 63-68, 発行日 1995-11-17 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
