| 講演名 | 2018-10-26 2-dispersion問題を解く近似アルゴリズム 天野 一幸(群馬大), 中野 眞一(群馬大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | Let $P$ be a set of points on the plane, and $d(p,q)$ be the distance between a pair of points $p,q$ in $P$. For a point $pin P$ and a subset $Ssubset P$ with $|S |ge 3$, the $2$-dispersion cost, denoted by $cost_2(p,S)$, of $p$ with respect to $S$is the sum of(1) the distance from $p$ to the nearest point in $S setminus{ p }$and(2) the distance from $p$ to the second nearest point in $S setminus{ p }$. The $2$-dispersion cost $cost_2(S)$ of $Ssubset P$ with $|S|ge 3$is $min_{pin S}{ cost_2(p,S) }$. Given a set $P$ of $n$ points and an integer $k$we wish to compute $k$ point subset $S$ of $P$with maximum $cost_2(S)$. In this paper we give a simple $1/({4sqrt{3}})$ approximation algorithmfor the problem. |
| キーワード(和) | |
| キーワード(英) | dispersion problemalgorithm |
| 資料番号 | COMP2018-26 |
| 発行日 | 2018-10-19 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2018/10/26(から1日開催) |
| 開催地（和） | 京都大学 |
| 開催地（英） | Kyoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG-JTITLE |
| タイトル（和） | 2-dispersion問題を解く近似アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Approximation Algorithm for the 2-Dispersion Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / dispersion problemalgorithm |
| 第 1 著者 氏名（和/英） | 天野 一幸 / Kazuyuki Amano |
| 第 1 著者 所属（和/英） | 群馬大学(略称：群馬大) Gunma University(略称：Gunma Univ.) |
| 第 2 著者 氏名（和/英） | 中野 眞一 / Shin-ichi Nakano |
| 第 2 著者 所属（和/英） | 群馬大学(略称：群馬大) Gunma University(略称：Gunma Univ.) |
| 発表年月日 | 2018-10-26 |
| 資料番号 | COMP2018-26 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | COMP-268 |
| ページ範囲 | pp.41-43(COMP), |
| ページ数 | 3 |
| 発行日 | 2018-10-19 (COMP) |