Given an ordered list of n items, p possible positions, and integer profits cij for assigning item i to position j, the order-preserving assignment problem consists of finding a profit-optimal assignment that assigns items to contiguous positions while preserving the original ranking, i.e., the highest-ranked item that will be assigned is assigned to position 1 and so on. Positions must be assigned contiguously starting with position one, but items need not be assigned to any particular position. The authors formulate the problem as a zero-one linear program, derive a minimal description of the associated polytope by linear inequalities, show that the diameter of the polytope equals two, and give a linear-time algorithm for the optimization problem, i.e., one that runs in time that is linear in the number of variables of the problem. They do this for both cases where at most p positions and where exactly p positions must be assigned and discuss briefly two modifications of the basic model.
