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:
- We first present an improved interior point method algorithm for exact s-t maximum flow on directed graphs that runs in time O(m4/3+o(1)U1/3) where U is the ratio of the maximum to minimum capacities on the edges.
- 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(√n(mn2 + mω + nω)log(1/ε)) time for an SDP with m constraints and n sized variable matrix, which improves over the previous results in a wide variety of regimes.
- 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(√n) with high probability. We then show that unlike previous such approaches, our approach may generalize to resolve matrix discrepancy problems.