Ilya Safro - Clemson University

Monday, March 7, 20116
Klaus 1116 West - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)

Title:
Multiscale Methods for Discrete Optimization on Graphs
Abstract:
In many real-world problems, a big scale gap can be observed between micro- and macroscopic scales of the problem because of the difference in mathematical (engineering, social, biological, physical, etc.) models and/or laws at different scales. The main objective of multigrid-inspired 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 discuss different strategies of creating these hierarchies for discrete optimization problems on large-scale graphs. These strategies are inspired by the classical multigrid frameworks such as geometric multigrid, algebraic multigrid and full approximation scheme. We will present in details a multiscale framework for linear arrangement, network compression, k-partitioning and clustering, network generation, sparsification, and epidemics response problems. Time permits, a multigrid-inspired algorithm for the support vector machines will be presented.

Url: http://people.cs.clemson.edu/~isafro/

Host: Richard Peng (rpeng@cc.gatech.edu)