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.