You are here

3-index assignment problems

Error message

Warning: uasort() expects parameter 1 to be array, null given in node_view_multiple() (line 2679 of /opt/www/data/drupal-7.34/modules/node/node.module).

Description

Assignment problems are among the best studied combinatorial optimization
problems. Typically, such a problem arises whenever the members of a first set have to be allocated/mapped to those of a second one in such a way that the overall cost is minimized. Studying k-tuples instead of pairs over k sets of equal size leads to multi-index assignment problems, in particular (k,s)-assignment problems, the parameter s indicating that every s-tuple of elements (each from a different set) is assigned to a (k-s)-tuple. For (k,s)=(2,1), for instance, we get back the classical 2-index assignment problem, and for s=1 or s=2 we obtain the family of axial or planar assignment problems, respectively. In the planar case and if k=3, any solution corresponds to a latin square, and if k=4  we come to mutually orthogonal latin squares (MOLS).


Assignment problems cover a large spectrum of applications:

  • time-tabling,
  • statistical design,
  • error-correcting codes,

to cite just a few. Our work on assignment problems goes back to the 1980's, when we studied planar 3-dimensional assignment problems with respect to their solvability by linear programming techniques, in other words: from a polyhedral point of view. At the same time we initiated a study on the completability of incomplete latin squares with the objective to describe those structures that could give an answer to the question: when is an incomplete latin square completable. Relations with class-teacher time table problems have also been investigated.

Our current work is on the completability of a particular type of incomplete latin rectangles and on open questions related to the existence of MOLS.

More complete information can be obtained here.

References

R.Euler, R.E.Burkard, R.Grommes, On latin squares and the facial structure of related polytopes,
Discrete Mathematics 62(1986)155-181.

R.Euler, Odd cycles and a class of facets of the axial 3-index assignment polytope,
Zastosowania Mathematyki XIX 3-4(1987)375-386.

R.Euler, H.Le Verge, Time-tables, polyhedra and the Greedy algorithm,
Discrete Applied Mathematics 65(1996)207-221.

R.Euler, On the completability of incomplete latin squares,
European Journal of Combinatorics 31(2010)535-552.

R.Euler, When is an incomplete (3,n)-Latin rectangle completable?
Rapport technique, Lab-STICC UMR CNRS 3192,
mars 2011, invited presentation: 24th European Conference on Operational
Research, July 2010, Lisbon, and: 5th World Conference on 21st Century
Mathematics, February 2011, Lahore, submitted.