| Item type |
SIG Technical Reports(1) |
| 公開日 |
2014-11-13 |
| タイトル |
|
|
タイトル |
Approximating the Colorful Caratheodory Theorem |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Approximating the Colorful Caratheodory Theorem |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
Institut fur Informatik, Freie Universitat Berlin |
| 著者所属 |
|
|
|
Institut fur Informatik, Freie Universitat Berlin |
| 著者所属(英) |
|
|
|
en |
|
|
Institut fur Informatik, Freie Universitat Berlin |
| 著者所属(英) |
|
|
|
en |
|
|
Institut fur Informatik, Freie Universitat Berlin |
| 著者名 |
Wolfgang, Mulzer
Yannik, Stein
|
| 著者名(英) |
Wolfgang, Mulzer
Yannik, Stein
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Let P1,..., Pd+1 ⊂ Rd be point sets whose convex hulls each contain the origin. Each set represents a color class. The Colorful Caratheodory theorem guarantees the existence of a colorful choice, i.e., a set that contains exactly one point from each color class, whose convex hull also contains the origin. So far, the computational complexity of computing such a colorful choice is unknown and thus approximation algorithms are of interest. We consider a new notion of approximation: a set C′ is called an m-colorful choice if it contains at most m points from each color class. We show that for all constant ε > 0, an ε(d+1)-colorful choice containing the origin in its convex hull can be found in polynomial time. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
Let P1,..., Pd+1 ⊂ Rd be point sets whose convex hulls each contain the origin. Each set represents a color class. The Colorful Caratheodory theorem guarantees the existence of a colorful choice, i.e., a set that contains exactly one point from each color class, whose convex hull also contains the origin. So far, the computational complexity of computing such a colorful choice is unknown and thus approximation algorithms are of interest. We consider a new notion of approximation: a set C′ is called an m-colorful choice if it contains at most m points from each color class. We show that for all constant ε > 0, an ε(d+1)-colorful choice containing the origin in its convex hull can be found in polynomial time. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2014-AL-150,
号 28,
p. 1-6,
発行日 2014-11-13
|
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL14150028.pdf (1.1 MB)
