Dissertation Talk: Fast Approximation Algorithms for Positive Linear Programs

Seminar | May 4 | 2-3 p.m. | 380 Soda Hall

 Di Wang

 Electrical Engineering and Computer Sciences (EECS)

Positive linear programs (LPs) are LPs formulated with non-negative coefficients, non-negative constraints and non-negative variables. This class of LPs models a wide range of fundamental problems in combinatorial optimization and operations research, thus have long drawn interest in theoretical computer science. Notable special cases include packing LPs and covering LPs, which apply to most resource allocation problems.

Although one can use general LP solvers such as interior-point method to solve positive LPs with high precision, i.e. $\log(1/\epsilon)$ convergence for $\epsilon$-approximate solution, such algorithms usually have very high computation cost, as operations such as the computation of the Hessian and matrix inversion are involved. With the abundance of large-scale data-sets, fast low precision iterative solvers are of great interest. Such solvers compute approximate solutions usually in time (or total work for parallel solvers) with nearly linear dependence
on the problem size, and $poly(1/\epsilon)$ dependence on the approximation parameter $\epsilon$.

We study iterative solvers with faster convergence for positive LPs, and achieve improved algorithms, both sequential and parallel, for positive LPs, as well as the special cases of packing LPs and covering LPs. In particular, we design various algebraic and combinatorial techniques, and organically integrate them in the algorithms.