Premium
Order‐preserving assignments
Author(s) -
Padberg Manfred,
Alevras Dimitris
Publication year - 1994
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199404)41:3<395::aid-nav3220410307>3.0.co;2-w
Subject(s) - linear programming , mathematics , combinatorics , polytope , position (finance) , integer programming , order (exchange) , integer (computer science) , ranking (information retrieval) , computer science , algorithm , artificial intelligence , finance , economics , programming language
Given an ordered list of n items, p possible positions, and integer profits c ij 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. We 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. We 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. © 1994 John Wiley & Sons, Inc.