[Colloquium] Seminar Announcement: Multi-Scale Algorithms for Combinatorial Optimization Problems - TODAY!

[Ninfa Mayorga]

Computation Institute- Data Lunch Seminar (DLS)

Speaker: Dr. Ilya Safro, Mathematics and Computer Science Division,  
Argonne National Laboratory
Date: March 25, 2011
Time: 12:00 PM - 1:00 PM
Location: The University of Chicago, Searle 240B, 5735 S. Ellis Avenue

Multi-Scale Algorithms for Combinatorial Optimization Problems

Abstract:
In many cases, a big scale gap can be observed between micro- and  
macroscopic scales of problems because of the difference in  
mathematical (engineering, social, biological, physical, etc.) models  
and/or laws at different scales. The main objective of multiscale  
algorithms is to create a hierarchy of problems, each representing the  
original problem at different coarse scales with fewer degrees of  
freedom. We will talk about different strategies of creating these  
hierarchies for large-scale combinatorial optimization problems:  
linear ordering, network compression, partitioning, clustering and  
constrained 2D-layout problem. These strategies are inspired by 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  
multiscale algorithm for the linear ordering problems. Our multiscale  
methods have proved themselves to be robust both as a first  
approximation and as more aggressive optimization solvers.

Bio:
Ilya Safro studied Mathematics and Computer Science at the Weizmann  
Institute of Science where he obtained his Ph.D. under the supervision  
of Achi Brandt and Dorit Ron. Currently, he is an Argonne Scholar at  
the Laboratory of Advanced Numerical Simulations at Argonne National  
Laboratory. His research interests include multiscale methods, network  
analysis, combinatorial optimization and machine learning.


Information: Lunch will be provided.  Please note location of talk  
will be in room 240B this week