UC Berkeley

Over the last few decades, the design of algorithms for combinatorial problems has benefited greatly from a continous optimization perspective. In this dissertation, we will focus on some specific ideas from continous optimization, particularly so-called interior point methods (IPMs), for the design of efficient algorithms for some combinatorial problems in theoretical computer science. We will present algorithms for three different applications using these ideas:

1) We first present an improved interior point method algorithm for exact $s$-$t$ maximum flow on directed graphs that runs in time $O(m^{4/3+o(1)}U^{1/3})$ where $U$ is the ratio of the maximum to minimum capacities on the edges.2) We then design a faster interior point method for the class of semi-definite programs (SDPs), a class of convex programs that have led to polynomial time algorithms for a variety of problems in combinatorial optimization, statistics and machine learning. Our algorithm runs in $O(\sqrt{n} (mn^2 + m^\omega + n^\omega)\log(1/\varepsilon))$ time for an SDP with $m$ constraints and $n$ sized variable matrix, which improves over the previous results in a wide variety of regimes. 3) We present a constructive proof of the Spencer problem by designing a Stieltjes transform based barrier function and running a random walk analyzed using this barrier function which gives a signing with discrepancy of $O(\sqrt{n})$ with high probability. We then show that unlike previous such approaches, our approach may generalize to resolve matrix discrepancy problems.