We provide novel dissipativity conditions for bounding the incremental L1 gain of systems. Moreover, we adapt existing results on the L∞ gain to the incremental setting and relate the incremental L1 and L∞ gain bounds through transposed systems. Building on work on optimization based approaches to constructing polyhedral Lyapunov functions, we make use of these conditions to obtain a Linear Programming based algorithm that can provide increasingly sharp bounds on the gains as a function of a given candidate polyhedral storage function or polyhedral set. The algorithm is also extended to allow for the design of constrained linear feedback controllers for performance, as measured by the bounds on the incremental gains. We apply the algorithm to a couple of numerical examples to illustrate the power, as well as some limitations, of this approach.