Faster Approximation Algorithms for
Packing and Covering Problems
Garud Iyengar
Department of Industrial Engineering and Operations Research
Columbia University
Wednesday, October 20, 2004
4:30 - 5:45 PM
Terman Engineering Center, Room 453
Abstract:
In this talk we will discuss how to adapt a method proposed by
Nesterov to design an algorithm that computes eps-optimal solutions to
fractional packing problems by solving O(\sqrt{Kn}/eps) separable
convex quadratic programs, where K denotes the maximum number of
non-zeros per row and n denotes the the number of variables. We
show that the quadratic program can be approximated to any degree of
accuracy by an appropriately defined piecewise-linear program.
For the special case of the maximum concurrent flow problem with
rational capacities and demands the general algorithm can be modified
to compute eps-optimal flow by solving shortest path problems -- the
number of shortest paths that need to be computed grow as
O(1/eps(\log(1/eps))) in eps, and polynomially in the size of the
problem. In contrast, previous algorithms requires Omega(1/eps^2)
iterations.
Extensions to the maximum multicommodity flow problem, covering
problems and mixed packing-covering problems will be described. Time
permitting we will also describe how these techniques also lead to
faster approximation algorithms for solving the SDP relaxation to the
maxcut and graph coloring problems.
Bio:
Garud Iyengar received a Ph.D. in Electrical Engineering from Stanford
University in 1999. He is currently an Associate Professor in the the
Industrial Engineering and Operations Research Department at Columbia
University.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html