40 KAM Mathematical Colloquium

Prof. RAINER E. BURKARD

Technische Universitaet Graz

SELECTED TOPICS ON ASSIGNMENT PROBLEMS

March 15, 2001 Lecture Room S3, Charles University, Malostranske nam. 25, Praha 1 14:00 PM

Abstract

Assignment problems play a central role in mathematical programming, having been studied for more than 50 years. In this survey we discuss recent developments in the areas of bipartite matching as well as linear and quadratic assignment problems. Among other topics, we describe a unifying algebraic theory for handling different objective functions and discuss the different asymptotic behaviour of linear and quadratic assignment problems. In particular we point out that the strange asymptotic behaviour of quadratic assignment problems can be derived by means of thermodynamical considerations.