講演名	2014/11/13 Approximating the Colorful Caratheodory Theorem ,
PDFダウンロードページ	PDFダウンロードページへ
抄録(和)
抄録(英)	Let P_1, ... , P_ ⊂ be 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)1-colorful choice containing the origin in its convex hull can be found in polynomial time.
キーワード(和)
キーワード(英)
資料番号	Vol.2014-AL-150 No.28
発行日

研究会情報
研究会	MSS
開催期間	2014/11/13(から1日開催)
開催地（和）
開催地（英）
テーマ（和）
テーマ（英）
委員長氏名（和）
委員長氏名（英）
副委員長氏名（和）
副委員長氏名（英）
幹事氏名（和）
幹事氏名（英）
幹事補佐氏名（和）
幹事補佐氏名（英）

講演論文情報詳細
申込み研究会	Mathematical Systems Science and its applications(MSS)
本文の言語	ENG
タイトル（和）
サブタイトル（和）
タイトル（英）	Approximating the Colorful Caratheodory Theorem
サブタイトル（和）
キーワード(1)（和/英）
第 1 著者 氏名（和/英）	/ WOLFGANG MULZER
第 1 著者 所属（和/英）	Institut fur Informatik, Freie Universitat Berlin
発表年月日	2014/11/13
資料番号	Vol.2014-AL-150 No.28
巻番号（vol）	vol.114
号番号（no）	313
ページ範囲	pp.-
ページ数	6
発行日