For several NP-hard network design problems, the best known approximation algorithms are remarkably simple randomized algorithms called Sample-Augment 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 Sample-Augment algorithms, i.e. to specify a specific sample for which the cost of the solution created by the Sample-Augment algorithm is at most a constant factor away from optimal. Our approach allows us to give deterministic versions of the Sample-Augment 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, 2-stage rooted stochastic Steiner tree problem with independent decisions, the a priori traveling salesman problem and the single sink buy-at-bulk problem. This partially answers an open question in Gupta et al.

Date:	10:40-11:20, Thursday, March 26, 2009

Venue:	FIT Building 1-315, 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 primal-dual method.

Abstract:	For several NP-hard network design problems, the best known approximation algorithms are remarkably simple randomized algorithms called Sample-Augment 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 Sample-Augment algorithms, i.e. to specify a specific sample for which the cost of the solution created by the Sample-Augment algorithm is at most a constant factor away from optimal. Our approach allows us to give deterministic versions of the Sample-Augment 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, 2-stage rooted stochastic Steiner tree problem with independent decisions, the a priori traveling salesman problem and the single sink buy-at-bulk problem. This partially answers an open question in Gupta et al.