  Max-plus based methods have been recently developed to approximate the value
function of possibly high dimensional optimal control problems. A critical step
of these methods consists in approximating a function by a supremum of a small
number of functions (max-plus "basis functions") taken from a prescribed
dictionary. We study several variants of this approximation problem, which we
show to be continuous versions of the facility location and $k$-center
combinatorial optimization problems, in which the connection costs arise from a
Bregman distance. We give theoretical error estimates, quantifying the number
of basis functions needed to reach a prescribed accuracy. We derive from our
approach a refinement of the curse of dimensionality free method introduced
previously by McEneaney, with a higher accuracy for a comparable computational
cost.
