Skip to main navigation Skip to Content

Computer Science

University of Toronto
  • Quercus
  • Student Support
  • Contact
  • About
    • History of U of T Computer Science
    • Computer Science at U of T Mississauga
    • Computer Science at U of T Scarborough
    • Employment Opportunities for Faculty/Lecturers
    • How to Find Us
    • Contact
  • 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: Nov 16
  • About
  • Undergraduate
  • Graduate
  • Research
  • People
  • News & Events

Theory Seminar: Nov 16

Event date: Friday, November 16, 2018, from 11:00 AM to 12:00 PM
Location: Galbraith Building, 35 St. George Street, Room 405

Title: Approximation Algorithms for Distributionally Robust Stochastic Optimization
Speaker: Chaitanya Swamy, University of Waterloo

Date: Friday, November 16
Time: 11 AM - 12 PM
Location: Galbraith Building, 35 St. George Street, Room 405

Abstract:
Two-stage stochastic optimization is a widely-used framework for modeling uncertainty, where we have a probability distribution over possible realizations of the data, called scenarios, and decisions are taken in two stages: we make first-stage decisions knowing only the underlying distribution and before a scenario is realized, and may take additional second-stage recourse actions after a scenario is realized. The goal is typically to minimize the total expected cost. A common criticism levied at this model is that the underlying probability distribution is itself often imprecise! To address this, an approach that is quite versatile and has gained popularity in the operations-research literature is the distributionally-robust 2-stage model: given a collection $\mathcal{D}$ of probability distributions, our goal now is to minimize the maximum expected total cost with respect to a distribution in $\mathcal{D}$.

There has been almost no prior work however on developing approximation algorithms for distributionally-robust problems, when the underlying scenario-set is discrete, as is the case with discrete-optimization problems. We provide a framework for designing approximation algorithms in such settings when the collection $\mathcal{D}$ is a ball around a central distribution. We use this to obtain approximation algorithms for the distributionally-robust versions of a variety of discrete-optimization problems including set cover, vertex cover, facility location, Steiner tree, with guarantees that are, in most cases, within $O(1)$-factors of the guarantees known for the deterministic version of the problem.

This is joint work with Andre Linhares. The talk will be self-contained.


All rights reserved copyright Computer Science, University of Toronto | Site Map