Date:  10:4011:20, Thursday, March 26, 2009 
Venue:  FIT Building 1315, Tsinghua University 
Title:  Deterministic Sampling Algorithms for Network Design

Speaker:  Anke van Zuylen 
Biography: 
Anke van Zuylen is a Postdoctoral Researcher at the Institute for Theoretical Computer Science at Tsinghua University. She received an M.A. degree in EconometrITCS and Operations Research from the Vrije University in Amsterdam in 2000, and a Ph.D. degree in Operations Research from Cornell University in 2008.
Her research interests are in combinatorial optimization problems arising in information science, network design and mechanism design. In particular, she is interested in developing and analyzing efficient algorithms using techniques from mathematical programming such as linear programming and the primaldual method.

Abstract: 
For several NPhard network design problems, the best known approximation algorithms are remarkably simple randomized algorithms called SampleAugment algorithms [Gupta, Kumar, Pal, and Roughgarden '03]. The algorithms draw a random sample from the input, solve a certain subproblem on the random sample, and augment the solution for the subproblem to a solution for the original problem. In this talk, I will discuss a general framework that allows us to derandomize most SampleAugment algorithms, i.e. to specify a specific sample for which the cost of the solution created by the SampleAugment algorithm is at most a constant factor away from optimal. Our approach allows us to give deterministic versions of the SampleAugment algorithms for the connected facility location problem, in which the open facilities need to be connected by either a tree or a tour, the virtual private network design problem, 2stage rooted stochastic Steiner tree problem with independent decisions, the a priori traveling salesman problem and the single sink buyatbulk problem. This partially answers an open question in Gupta et al.
