Joint ACO/DOS - Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions

Other Talks
Wednesday, October 28, 2009 - 11:00
1 hour (actually 50 minutes)
ISyE Executive Classroom
ACO, Computing Science and Systems, Georgia Tech

Organizer: Daniel Dadush, ACO Student, ISyE

Applications in complex systems such as the Internet have spawned recent interest in studying situations involving multiple agents with their individual cost or utility functions. We introduce an algorithmic framework for studying combinatorial problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems (Vertex Cover, Shortest Path, Perfect Matching, and Spanning Tree) in this setting and establish tight upper and lower bounds for the approximability of these problems. This talk is based on joint work with Gagan Goel, Chinmay Karande and Wang Lei. This is a joint ACO/DOS seminar, so please come a little early for pizza and refreshments sponsored by ACO.