# Improved Interior Point Methods for Some Structured Combinatorial Problems

### Tarun Kathuria

### EECS Department, University of California, Berkeley

### Technical Report No. UCB/EECS-2023-292

### December 19, 2023

### http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-292.pdf

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.

**Advisors:** Prasad Raghavendra

BibTeX citation:

@phdthesis{Kathuria:EECS-2023-292, Author= {Kathuria, Tarun}, Title= {Improved Interior Point Methods for Some Structured Combinatorial Problems}, School= {EECS Department, University of California, Berkeley}, Year= {2023}, Month= {Dec}, Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-292.html}, Number= {UCB/EECS-2023-292}, Abstract= {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.}, }

EndNote citation:

%0 Thesis %A Kathuria, Tarun %T Improved Interior Point Methods for Some Structured Combinatorial Problems %I EECS Department, University of California, Berkeley %D 2023 %8 December 19 %@ UCB/EECS-2023-292 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-292.html %F Kathuria:EECS-2023-292