Convex Optimization With Combinatorial Characteristics: New Algorithms for Linear Programming, Min-Cost Flow, and Other Structured Problems

Abstract

This thesis focuses on algorithmic questions arising from discrete mathematics, with a particular emphasis on optimization on planar graphs. Historically, research in this area followed in one of two approaches: 1). Design problem-specific algorithms that are combinatorial in nature and make use of structures in the underlying discrete object, and 2). Cast the problem as a general optimization problem, typically a linear program (LP), and apply a general-purpose LP solver. My work unifies the two approaches in the design and analysis of fast algorithms, guided by the question: How can we customize general-purpose convex optimization techniques to apply to problems with significant underlying structural properties? By combining a wide-ranging set of tools under this paradigm, including convex analysis, sketching algorithms, data structures, numerical linear algebra, and structural combinatorics, we are able to design new algorithms for cornerstone problems in theoretical computer science, with runtimes that are significant improvements over the existing state-of-the-art. This thesis contains the following results:

1. The first high-accuracy LP solver for α-separable LPs with n constraints and m variables. The algorithm runs in Õ(m^1/2+2α) time, compared to the previous best Õ(m^ω) time with no consideration for separability, where ω ≈ 2.37 is the matrix-multiplication constant. A special case here is planar LPs in Õ(n^1.5) time;

2. The fastest algorithm to solve min-cost flow on planar graphs with n vertices in Õ(n) time, which is nearly-optimal, and predates the current best almost-optimal algorithm for general graphs;

3. The first high-accuracy LP solver for LPs with n constraints, m variables, and treewidth τ. The algorithm runs in Õ(mτ^(ω+1)/2) time;

4. The first algorithm to solve min-cost flow on graphs with treewidth τ, running in Õ(mτ^1/2 + nτ) time;

5. The fastest algorithm to solve k-commodity flow on planar graphs on n vertices in Õ(k^2.5n^1.5) time, compared to the previous best Õ(k^ωn^ω) time with no consideration for planarity;

6. The fastest algorithm to compute circle-packing representations of planar graphs, with an improvement of a cubic factor over the existing algorithm.