Gerhard Reinelt (University of Heidelberg)


Ordering Problems


Manifold combinatorial optimization problems are concerned with the determination of optimal orderings of objects subject to various types of constraints and objectives. In particular, the objective function has a big influence on the difficulty of an ordering problem and on suitable optimization algorithms. Some examples are the linear ordering problem, the sequential ordering problem, the linear arrangement problem and the target visitation problem.  In this course we survey some of these problems and discuss techniques and approaches for solving them to optimality. Some old and a couple of new results are reviewed.