A polynomial algorithm for packing unit squares in a hypograph of a piecewise linear function

Abstract

We consider the problem of packing the maximal number of unit squares in a hypograph of a function. A polynomial time algorithm is described to solve this problem for a piecewise linear function.

Keywords

• packing unit squares
• polynomial algorithm