ORIE Colloquium: Zhuan Khye (Cedric) Koh (Boston U.)

Recent Advances in Exact and Approximate Linear Programming

Linear programs (LPs) can be solved in polynomial time using the ellipsoid method or interior point methods. However, their running time depends on the size of the numbers in the input, which can be unbounded in the problem dimension. It is a major open question whether LPs can be solved in strongly polynomial time. Given an LP with m variables and n constraints, a strongly polynomial algorithm must compute an optimal solution using only poly(m,n) elementary arithmetic operations, independent of the size of the coefficients describing the LP. This question was first asked by Megiddo in 1983 and is now popularly referred to as Smale’s 9th problem.

In the first part of this talk, we present a strongly polynomial algorithm for minimum cost generalized flow, and as a consequence, for all LPs with at most two variables per inequality. Previously, strongly polynomial algorithms were only known for the primal and dual feasibility problems. This provides a next milestone towards answering Smale’s 9th problem.

The second part of this talk focuses on implicit LPs, which commonly arise as relaxations to combinatorial optimization problems. Even though they can be solved using the ellipsoid method given a separation oracle, it is impractical for large-scale problems. For this reason, there has been tremendous effort in developing fast approximate solvers using the multiplicative weights update (MWU) framework. We give a generic method for accelerating the MWU framework for implicit packing/covering LPs. We show how it yields parallel approximation schemes for the Held-Karp bound of metric TSP and the k-edge-connected spanning subgraph LP, with near-optimal work and depth.

Bio: Zhuan Khye (Cedric) Koh is a postdoc at Boston University. Previously, he was at CWI Amsterdam, working in the Networks & Optimization group. He studied mathematics at the University of Waterloo and completed his Ph.D. at the London School of Economics. His research interests are in combinatorics and optimization, with a particular focus on the interplay between combinatorial optimization and continuous optimization.