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. In the talk, I will illustrate our approach by focusing on the Single-Source Rent-or-Buy problem in which we are given an undirected graph, costs for renting the edges, a blow-up factor M, a source and a set of sinks that need to be connected to the source. We can either rent an edge for use by a specific sink, or we can buy the edge, which costs M times the renting cost, but allows any sink to use the edge.

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 Econometrics 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. She has won the best student paper award at the European Symposium on Algorithms (ESA 2008) and the Netherlands Society for Statistics and Operations Research Thesis Award 2001 (together with Frans Schalekamp), and received an honorable mention in the Nicholson student paper competition.