Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
Why Study CS at U of T
Career Options
History of DCS
Giving to DCS
Computer Science at UofT Mississauga
Computer Science at UofT Scarborough
Contact
Employment Opportunities for Faculty/Lecturers
How to Find Us
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate students
Current Graduate students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar - Feb 22
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar - Feb 22
Event date: Friday, February 22, 2013, at 11:10 AM
Location: GB 248
Speaker: Alina Ena
University of Illinois
Title: Submodular cost allocation: applications, algorithms and hardness results
Abstract:
Discrete optimization problems follow a common template: given a set function f on a ground set V, find the subset S of V that maximizes or minimizes f(S) subject to certain constraints on S. If f is a linear function, this framework captures fundamental combinatorial optimization problems. In this talk, we consider optimization problems in which the function f belongs to the more general class of submodular functions. Submodular optimization problems are motivated by several applications and they are of mathematical interest.
In this talk, we identify a class of submodular minimization problems that are tractable. We introduce a model that captures allocation problems with submodular costs and we give a generic approach for designing approximation algorithms for problems in this model. Our model captures several problems of interest, such as non-metric facility location, multiway cut problems in graphs and hypergraphs, uniform metric labeling and its generalization to hub location. We describe a convex-programming relaxation obtained via the Lovasz extension of a submodular function. This allows us to understand several previous relaxations and rounding procedures in a uniļ¬ed fashion and also develop new formulations and approximation algorithms for several problems. We complement our algorithmic results with hardness of approximation results for some of the problems in this model.
This talk is based on joint work with Chandra Chekuri, Jan Vondrak, and Yi Wu.