A lecture on Yet another sort by Peter Widmayer

(NoNA Spring School on Algorithms, Istanbul, 12-15 March, 2009)

Abstract

We study the problem of bringing the cars of a train in a yard into a desired order, with minimum effort. We show how simple versions of this combinatorial optimization problem can be solved easily, while other versions are hard.