This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Volgenant, A. Search for Related Content

Technical Note—A Note on Parametric Analysis in Linear Assignment

Operations Research Group, Faculty of Economics and Econometrics, University of Amsterdam, 1018 WB Amsterdam, The Netherlands
a.volgenant{at}uva.nl

A classic application of the linear assignment problem is the assignment of people to jobs (or jobs to people). In this context, it is interesting to measure competition for jobs and to generate a suitable list of jobs from which a person can choose; the length of the list is a parameter. A known list-generation procedure is based on an interior-point method followed by a parametric analysis. We describe a more efficient procedure, exploiting linear assignment theory and shortest-path computations. Further, we propose an alternative list-generation procedure, based on a special type of dual values for the linear assignment problem.

Subject classifications: assignment problems; matchings; parametric analysis.
History: Received December 2005; revision received April 2007; accepted April 2007.