Order‐preserving assignments

Manfred Padberg and Dimitris Alevras

Naval Research Logistics (NRL), 1994, vol. 41, issue 3, 395-421

Abstract: 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. 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.

Date: 1994
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199404)41:33.0.CO;2-W

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:41:y:1994:i:3:p:395-421

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().