  In this work, we study the problem of finding approximate, with minimum
support set, solutions to matrix max-plus equations, which we call sparse
approximate solutions. We show how one can obtain such solutions efficiently
and in polynomial time for any $\ell_p$ approximation error. Based on these
results, we propose a novel method for piecewise-linear fitting of convex
multivariate functions, with optimality guarantees for the model parameters and
an approximately minimum number of affine regions.
