Seminars

View all Seminars  |  Download ICal for this event

The interplay between Algorithms, Structure and Optimization, via Densest Subgraph

Series: Department Seminar

Speaker: Prof. Chandra Chekuri, Paul and Cynthia Saylor Professor, Department of Computer Science, University of Illinois, Urbana-Champaign, and Smt Rukmini-Sri Gopalakrishnachar Visiting Chair Professo

Date/Time: Jul 12 16:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
The densest subgraph problem in a graph (DSG) is a simple to state
problem that has several applications in data mining and network
analysis. It is part of a larger class of problems that come under the
umbrella of dense subgraph discovery. A polynomial-time algorithm for
DSG is known via a classical reduction to network flow. However,
large graphs that arise in modern data analysis have motivated the
design of several fast approximation algorithms that are simple to
implement and work well in practice. In recent work we showed that a
simple iterative peeling algorithm called Greedy++ converges to a near-optimal
solution. The proof and subsequent developments illustrate the
interplay between algorithms/heuristics, structural understanding, and
the synergy between discrete and continuous optimization. The talk
will describe some of these developments.

Speaker Bio:
Chandra Chekuri is the Paul and Cynthia Saylor Professor in the Department of Computer Science at the University of Illinois, Urbana-Champaign, and the current Smt Rukmini - Sri Gopalakrishnachar Visiting Chair Professor at the Indian Institute of Science. He joined the University of Illinois in 2006 after spending eight years at Lucent Bell Labs. Prior to that he received his PhD from Stanford University in 1998, and an undergraduate degree from IIT Madras in 1993. He is interested in design and analysis of algorithms, combinatorial optimization, and theoretical computer science. He recently became an ACM Fellow for his contributions to approximation algorithms and submodular optimization.

Host Faculty: Prof. Arindam Khan