  Let $C_1,\dots,C_{d+1}\subset \mathbb{R}^d$ be $d+1$ point sets, each
containing the origin in its convex hull. We call these sets color classes, and
we call a sequence $p_1, \dots, p_{d+1}$ with $p_i \in C_i$, for $i = 1, \dots,
d+1$, a colorful choice. The colorful Carath\'eodory theorem guarantees the
existence of a colorful choice that also contains the origin in its convex
hull. The computational complexity of finding such a colorful choice (CCP) is
unknown. This is particularly interesting in the light of polynomial-time
reductions from several related problems, such as computing centerpoints, to
CCP.
  We define a novel notion of approximation that is compatible with the
polynomial-time reductions to CCP: a sequence that contains at most $k$ points
from each color class is called a $k$-colorful choice. We present an algorithm
that for any fixed $\varepsilon > 0$, outputs an $\lceil \epsilon
d\rceil$-colorful choice containing the origin in its convex hull in polynomial
time.
  Furthermore, we consider a related problem of CCP: in the nearest colorful
polytope problem (NCP), we are given sets $C_1,\dots,C_n\subset\mathbb{R}^d$
that do not necessarily contain the origin in their convex hulls. The goal is
to find a colorful choice whose convex hull minimizes the distance to the
origin. We show that computing a local optimum for NCP is PLS-complete, while
computing a global optimum is NP-hard.
