Modern Aspects of Submodularity

 

Date: March 19th - March 22nd, 2012
Location: Klaus Advanced Computing building

Workshop Theme

Submodular functions are discrete analogues of convex functions, arising in various fields of computer science and operations research. Since the seminal work of Jack Edmonds (1970), submodularity has long been recognized as a common structure of many efficiently solvable combinatorial optimization problems. Recent algorithmic developments in the past decade include combinatorial strongly polynomial algorithm for minimization, constant factor approximation algorithms for maximization, and efficient methods for learning submodular functions. In addition, submodular functions find novel applications in combinatorial auctions, machine learning, and social networks. This workshop aims at providing a forum for researchers from a variety of backgrounds for exchanging results, ideas, and problems on submodular optimization and its applications. The first day will be devoted to tutorial-style lectures!

Speakers:

Jeff Bilmes (University of Washington), Chandra Chekuri (UIUC), Satoru Fujishige (Kyoto University), Gagan Goel (Google Research), Michel Goemans (MIT), Carlos Guestrin (CMU), Nick Harvey (UBC), Satoru Iwata (Kyoto University), Kamal Jain (e-Bay), Andreas Krause (ETH), Jon Lee (U. Michigan), Tom McCormick (UBC), Aranyak Mehta (Google Research), Vahab Mirrokni (Google Research), Kazuo Murota (University of Tokyo), Kiyohito Nagano (University of Tokyo), Maurice Queyranne (UBC), Amin Saberi (Stanford), Akiyoshi Shioura (Tohoku University), Maxim Sviridenko (IBM), Zoya Svitkina (Google), Jan Vondrak (IBM), Laszlo Vegh (Georgia Tech).

Schedule

Abstracts of presentations

March 19 (Monday)
Tutorial lectures by Krause, Murota and Vondrak:

9:20 -- 9:30 Welcome and Introduction
9:30 -- 10:20 Jan Vondrak - IBM
10:20 -- 10:50 --- coffee break ---
10:50 -- 11:40 Andreas Krause - ETH
11:50 -- 12:40 Andreas Krause
-------- Lunch break --------
14:00 -- 14:50 Kazuo Murota - University of Tokyo
14:50 -- 15:10 --- coffee break ---
15:10 -- 16:00 Kazuo Murota
16:10 -- 17:00 Jan Vondrak

March 20 (Tuesday)

9:30 -- 10:10 Chandra Chekuri - UIUC
10:10 -- 10:30 --- coffee break ---
10:30 -- 11:10 Zoya Svitkina - Google
11:20 -- 12:00 Gagan Goel - Google Research
------- Lunch break -------
13:30 -- 14:10 Maxim Sviridenko - IBM
14:10 -- 14:30 --- coffee break ---
14:30 -- 15:10 Jon Lee - U. Michigan
15:20 -- 16:00 Akiyoshi Shioura - Tohoku University
16:10 -- 16:50 Vahab Mirrokni - Google Research

 March 21 (Wednesday)

9:30 -- 10:10 Jeff Bilmes - University of Washington
10:10 -- 10:30 --- Coffee Break ---
10:30 -- 11:10 Kiyohito Nagano - University of Tokyo
11:20 -- 12:00 Vijay Vazirani - Georgia Tech
-------- Lunch Break ------
13:30--14:10 Michel Goemans - MIT
14:10 -- 14:30 -- Coffee Break --
14:30 -- 15:10 Amin Saberi - Stanford
15:20 -- 16:00 Satoru Fujishige - Kyoto University
16:10 -- 16:50 Maurice Queyranne - UBC
17:00 -- 17:40 Carlos Guestrin (CMU)

March 22 (Thursday)

9:30 -- 10:10 Andrei Krokhin - Durham University, UK
10:10 -- 10:30 -- Coffee Break --
10:30 -- 11:10 Kamal Jain - e-Bay
11:20 -- 12:00 Aranyak Mehta - Google Research
-------- Lunch Break --------
13:30 -- 14:10 Tom McCormick - UBC
14:10 -- 14:30 -- Coffee Break --
14:30 -- 15:10 Laszlo Vegh - Georgia Tech
15:20 -- 16:00 Satoru Iwata - Kyoto University
16:10 -- 16:50 Prasad Raghavendra - Georgia Tech

Organizers

Shabbir Ahmed (School of ISyE, GaTech), Nina Balcan (School of CS, GaTech), Satoru Iwata (RIMS, Kyoto University), and Prasad Tetali (School of Math and School of CS, GaTech)

This event was sponsored by Algorithms & Randomness Center, ACO Ph.D. Program, the School of Math and the School of Industrial and Systems Engineering (Georgia Tech), Google Inc., Microsoft Corp. (USA), Yandex Corp. (Russia), IMA (Minnesota).