Sparsification, online optimization, and an almost-linear time algorithm for maximum flow
Abstract/Contents
- Abstract
- This thesis designs efficient algorithms for combinatorial and continuous optimization problems. By combining new techniques developed in this thesis pertaining to iterative methods, dynamic algorithms, and high-dimensional geometry, we give an almost-linear-time algorithm that computes an exact maximum flow and minimum cost flows in directed graphs. Our insights lead to algorithms for broader classes of combinatorial and continuous optimization problems including online discrepancy minimization, regression, and dynamic maxflow. In the first part of the thesis we study iterative methods, which are procedures which solve an optimization problem through a sequence of simpler subproblems. By understanding the geometry of the underlying optimization problem, we give iterative methods with improved convergence rates and runtimes for the problems of $\ell_p$ regression, maximum flow, and mincost flow. In the second part of the thesis we study dynamic algorithms and online optimization which naturally arise from studying iterative methods. In particular, we give the improved algorithms that maintain an approximate maximum flow in dynamic graphs undergoing edge insertions, and also nearly-optimal algorithms for minimizing the discrepancy of vectors arriving online. In the third part of the thesis, we study sparsification problems motivated by high-dimensional geometry. The goal of sparsification is to reduce the size of an objective while approximately maintaining the desired properties, such as the value on all inputs. We give improved and nearly-optimal size bounds for sparsification of several objectives including spectral hypergraph energies and sums of symmetric submodular functions. Finally, we give nearly-linear size bounds for sparsification of generalized linear models satisfying natural bounds on their growth, which imply nearly-optimal algorithms for solving $\ell_p$-regression for $p \in (1, 2]$. This thesis contains material from the papers \cite{KLS20, ALS20, LSS21, CKLPPS22, JLS22, JLS23, BLS23, JLLS23, JLLS23b}.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2023; ©2023 |
| Publication date | 2023; 2023 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Liu, Yang (Yang P.) |
|---|---|
| Degree supervisor | Sidford, Aaron |
| Degree supervisor | Vondrak, Ján, (Mathematician) |
| Thesis advisor | Sidford, Aaron |
| Thesis advisor | Vondrak, Ján, (Mathematician) |
| Thesis advisor | Charikar, Moses |
| Degree committee member | Charikar, Moses |
| Associated with | Stanford University, School of Humanities and Sciences |
| Associated with | Stanford University, Department of Mathematics |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Yang Liu. |
|---|---|
| Note | Submitted to the Department of Mathematics. |
| Thesis | Thesis Ph.D. Stanford University 2023. |
| Location | https://purl.stanford.edu/tn858wg4267 |
Access conditions
- Copyright
- © 2023 by Yang Liu
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...