• Calendar

May 11, Tuesday
12:00 – 14:00

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas. However multilevel techniques have not been widely applied to combinatorial optimisation problems. Inthis seminar we address the issue of multilevel algorithms for such problems. We have developed the multiscale algorithm for the Minimum Linear Arrangement Problem.

The Minimum Linear Arrangement problem is widely used and studied in many practical and theoretical applications. We will present a linear-time heuristics (without giving lower and upper bounds) for the problem inspired by the Algebraic Multigrid approach which is based on weighted edge contraction rather than simple contraction. Our results turned out to be better than every known result in almost all cases, while the short running time of the algorithm enabled experiments with very large graphs. Joint work with Dr. Dorit Ron and Prof. Achi Brandt.