Deterministic
Sampling Algorithms for Network Design
By

Dr.
Anke van Zuylen
Postdoctoral
Researcher, Institute for Theoretical Computer
Science
Tsinghua
University, Beijing

Date:
Feb 12, 2009 (Thursday) 
Time:
4:30p.m  5:30p.m 
Venue:
Rm. 121, Ho Sin Hang Engineering Building, CUHK 
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. In the talk, I will
illustrate our approach by focusing on the SingleSource
RentorBuy problem in which we are given an undirected
graph, costs for renting the edges, a blowup 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 primaldual 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.
