Representing Piecewise Linear Functions by Functions with Small Arity

A piecewise linear function can be described in different forms: as an arbitrarily nested expression of min- and max-functions, as a difference of two convex piecewise linear functions, or as a linear combination of maxima of affine-linear functions. In this paper, we provide two main results: first, we show that for every piecewise linear function there exists a linear combination of max-functions with at most n+1 arguments, and give an algorithm for its computation. Moreover, these arguments are contained in the finite set of affine-linear functions that coincide with the given function in some open set. Second, we prove that the piecewise linear function max(0, x1, ldots, xn) cannot be represented as a linear combination of maxima of less than n+1 affine-linear arguments. This was conjectured by Wang and Sun in 2005 in a paper on representations of piecewise linear functions as linear combination of maxima.