Presentation	2014/11/13 Approximating the Colorful Caratheodory Theorem WOLFGANG MULZER, YANNIK STEIN,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	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.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)
Paper #	Vol.2014-AL-150 No.28
Date of Issue

Conference Information
Committee	MSS
Conference Date	2014/11/13(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Mathematical Systems Science and its applications(MSS)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Approximating the Colorful Caratheodory Theorem
Sub Title (in English)
Keyword(1)
1st Author's Name	WOLFGANG MULZER
1st Author's Affiliation	Institut fur Informatik, Freie Universitat Berlin()
2nd Author's Name	YANNIK STEIN
2nd Author's Affiliation	Institut fur Informatik, Freie Universitat Berlin
Date	2014/11/13
Paper #	Vol.2014-AL-150 No.28
Volume (vol)	vol.114
Number (no)	313
Page	pp.pp.-
#Pages	6
Date of Issue