Assignment Problems: At the Roots of Combinatorial Optimization

In 1955 H. W. Kuhn published the Hungarian algorithm, the first polynomial-time algorithm for the assignment problem. In the next fifty years assignment problems attracted hundreds of researchers. Their studies accompanied and sometimes anticipated the development of Combinatorial Optimization, producing fundamental contributions to all algorithmic techniques in use nowadays. We review the most important assignment problems (linear, quadratic, bottleneck) and the most relevant results in this area. We also show that a recently discovered paper dated 1851 contains a solution method that appears to anticipate by one century the discovery of the Hungarian algorithm. Talk partially based on Assignment Problems by R. Burkard, M. Dell'Amico and S. Martello (SIAM, 2009) http://www.assignmentproblems.com

Prof. Alberto Marchetti Spaccamela, Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza"

Multiprocessor real-time scheduling: algorithms and complexity

A real-time task system consists of a finite number of tasks, each of which generates an infinite sequence of recurring jobs with the same processing requirement characterized by a deadline.

We distinguish two main classes of task systems, periodic and sporadic task systems, which differ in the generation of job sequences recurrence scheme. There is given one or multiple processors, each of which can process only one job at the time. Now, each job must be executed by the system, possibly with preemptions and migration, before its deadline. A task system is said to be feasible if there exists a schedule such that each job completes its execution requirement before its deadline.

We review complexity results for different variation of the problem. In the hope of overcoming hardness results, we also discuss different relaxations of the problem.

The above is joint work with V. Bonifaci, H.L. Chan, N.Megow, S.Stiller