Centre for Discrete and Applicable Mathematics

 CDAM Research Report, LSE-CDAM-2002-01

April 2002

Polyhedral results for assignment problems

D. Magos, I. Mourtos, and G. Appa


This paper introduces an Integer Programming model for multidimensional assignment problems and examines the underlying polytopes. It also proposes a certain hierarchy among assignment polytopes. The dimension for classes of multidimensional assignment polytopes is established, unifying and generalising previous results. The framework introduced constitutes the first step towards a polyhedral characterisation for classes of assignment problems. The generic nature of this approach is illustrated by identifying a family of facets for a certain class of multidimensional assignment problems, namely "axial" problems.

A PDF file (267 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2002-01, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7732.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

Introduction to the CDAM Research Report Series.
CDAM Homepage.

Copyright © London School of Economics & Political Science 2005

Last changed: Wed 9 Feb 2005
For comments go to: http://www.maths.lse.ac.uk/webmaster.html