Colloquium - Interplay of Discrete and Continuous Optimization: A Case Study via Submodular Function Maximization

Date: 
October 30, 2019 - 4:00pm to 5:00pm
Location: 
2229 SC
Speaker: 
Chandra Chekuri
Computer Science | University of Illinois, Urbana-Champaign

The interplay between discrete and continuous optimization has been an exciting theme in recent years. This talk will focus on submodular function maximization as a case study to demonstrate the power of this interplay. Some of the main results in this space have been obtained almost a decade ago. Recently there has been a new direction of interest, namely to find parallel and low-adaptivity algorithms. The talk will describe some of these recent developments. No prior background on submodular functions will be assumed.

Recent work on parallel algorithm is joint with Kent Quanrud.

Bio:

Chekuri profile pic UIUCChandra Chekuri is a Professor of Computer Science at the University of Illinois, Urbana-Champaign. He received his PhD from the Department of Computer Science at Stanford University in 1998, then worked as a Member of Technical Staff at Lucent Bell Labs from 1998 until 2006 before moving to Illinois. He is broadly interested in theoretical computer science and optimization. His main contributions have been to approximation algorithms for NP-Hard problems and related topics in mathematical programming, graph theory, and submodularity.