[Colloquium] THEORY SEMINAR: Ilya Safro, ANL on November 23, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, November 23, 2010 
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:		Ilya Safro

From:		Argonne National Laboratory

Web page:	http://www.mcs.anl.gov/~safro/

Title: 		 Multilevel algorithms for large-scale combinatorial optimization problems  

Abstract:  	 The main objective of multilevel algorithms (MA) is to create a hierarchy of problems, each representing the original problem, but with fewer degrees of freedom. We will talk about different strategies of creating these hierarchies for graph related NP-hard optimization problems: linear ordering problems (logarithmic and linear arrangements, 2-sum, bandwidth, workbound), (hyper)graph partitioning and constrained 2D-layout problem. These strategies are based on the classical multigrid frameworks: Geometric Multigrid, Algebraic Multigrid and Full Approximation Scheme. We will present in details a framework for designing linear time Algebraic Multigrid based MA for the minimum linear and logarithmic arrangement problems. Unfortunately, theoretical bounds for MA for combinatorial optimization problems are not known. Our algorithms were developed for practical purposes and we compared them to many different heuristics such as: spectral sequencing, optimally oriented decomposition tree, multilevel based, simulated annealing, genetic algorithms, path relinking, GRASP-based and others (including their combinations). For almost all large-scale instances, we observed significant improvement of the results and/or the computational time. Our MA have proved themselves to be very robust both as a first approximation and as more aggressive energy minimizers. If time allows, we will discuss the notion of algebraic distance between graph vertices. Algebraic distance is inspired by Bootstrap Algebraic Multigrid. It can be successfully used as ingredient of MA on graphs, and as a preprocessing for greedy choice steps in algorithms for various well know connectivity based problems (such as approximated maximum matching, approximated minimum independent set, TSP, etc.).

Refreshments will be served prior to the talk at 2:30 in Ryerson 255.