refs.bib

@article{thorup2005approximate,
  title={Approximate distance oracles},
  author={Thorup, Mikkel and Zwick, Uri},
  journal={Journal of the ACM (JACM)},
  volume={52},
  number={1},
  pages={1--24},
  year={2005},
  publisher={ACM New York, NY, USA}
}

@inproceedings{chechik2014approximate,
  title={Approximate distance oracles with constant query time},
  author={Chechik, Shiri},
  booktitle={Proceedings of the forty-sixth annual ACM symposium on Theory of computing},
  pages={654--663},
  year={2014}
}

@inproceedings{chechik2015approximate,
  title={Approximate distance oracles with improved bounds},
  author={Chechik, Shiri},
  booktitle={Proceedings of the forty-seventh annual ACM symposium on Theory of Computing},
  pages={1--10},
  year={2015}
}

@inproceedings{LS20a,
  title = {Faster Energy Maximization for Faster Maximum Flow},
  booktitle = {Proceedings of the 52nd {{Annual ACM SIGACT Symposium}} on {{Theory}} of {{Computing}}},
  author = {Liu, Yang P. and Sidford, Aaron},
  year = {2020},
  pages = {803--814},
  file = {/Users/rjkyng/Dropbox/Repos/papers/LS20a.pdf;/Users/rjkyng/Zotero/storage/KUUZNNT8/3357713.html}
}

@article{LS20b,
  title = {Faster {{Divergence Maximization}} for {{Faster Maximum Flow}}},
  author = {Liu, Yang P. and Sidford, Aaron},
  year = {2020},
  month = apr,
  abstract = {In this paper we provide an algorithm which given any \$m\$-edge \$n\$-vertex directed graph with integer capacities at most \$U\$ computes a maximum \$s\$-\$t\$ flow for any vertices \$s\$ and \$t\$ in \$m\^\{4/3+o(1)\}U\^\{1/3\}\$ time. This improves upon the previous best running times of \$m\^\{11/8+o(1)\}U\^\{1/4\}\$ (Liu Sidford 2019), \$\textbackslash tilde\{O\}(m \textbackslash sqrt\{n\} \textbackslash log U)\$ (Lee Sidford 2014), and \$O(mn)\$ (Orlin 2013) when the graph is not too dense or has large capacities. To achieve the results this paper we build upon previous algorithmic approaches to maximum flow based on interior point methods (IPMs). In particular, we overcome a key bottleneck of previous advances in IPMs for maxflow (M\textbackslash k\{a\}dry 2013, M\textbackslash k\{a\}dry 2016, Liu Sidford 2019), which make progress by maximizing the energy of local \$\textbackslash ell\_2\$ norm minimizing electric flows. We generalize this approach and instead maximize the divergence of flows which minimize the Bregman divergence distance with respect to the weighted logarithmic barrier. This allows our algorithm to avoid dependencies on the \$\textbackslash ell\_4\$ norm that appear in other IPM frameworks (e.g. Cohen M\textbackslash k\{a\}dry Sankowski Vladu 2017, Axiotis M\textbackslash k\{a\}dry Vladu 2020). Further, we show that smoothed \$\textbackslash ell\_2\$-\$\textbackslash ell\_p\$ flows (Kyng, Peng, Sachdeva, Wang 2019), which we previously used to efficiently maximize energy (Liu Sidford 2019), can also be used to efficiently maximize divergence, thereby yielding our desired runtimes. We believe both this generalized view of energy maximization and generalized flow solvers we develop may be of further interest.},
  archiveprefix = {arXiv},
  eprint = {2003.08929},
  eprinttype = {arxiv},
  file = {/Users/rjkyng/Dropbox/Repos/papers/LS20b.pdf;/Users/rjkyng/Zotero/storage/E6V5DQN5/2003.html},
  journal = {arXiv:2003.08929 [cs, math]},
  keywords = {Computer Science - Data Structures and Algorithms,Mathematics - Optimization and Control},
  primaryclass = {cs, math}
}





@inproceedings{DS08,
  title = {Faster Approximate Lossy Generalized Flow via Interior Point Algorithms},
  booktitle = {Proceedings of the Fortieth Annual {{ACM}} Symposium on {{Theory}} of Computing},
  author = {Daitch, Samuel I. and Spielman, Daniel A.},
  year = {2008},
  month = may,
  pages = {451--460},
  publisher = {{Association for Computing Machinery}},
  address = {{New York, NY, USA}},
  doi = {10.1145/1374376.1374441},
  abstract = {We present asymptotically faster approximation algorithms for the generalized flow problems in which multipliers on edges are at most 1. For this lossy version of the maximum generalized flow problem, we obtain an additive {$\epsilon$} approximation of the maximum flow in time O\{m3/2 log (U/{$\epsilon$})2\}, where m is the number of edges in the graph, all capacities are integers in the range \{1, ... , U\}, and all loss multipliers are ratios of integers in this range. For minimum cost lossy generalized flow with costs in the range \{1,... ,U\}, we obtain a flow that has value within an additive {$\epsilon$} of the maximum value and cost at most the optimal cost. In many parameter ranges, these algorithms improve over the previously fastest algorithms for the generalized maximum flow problem by a factor of m1/2 and for the minimum cost generalized flow problem by a factor of approximately m1/2/ {$\epsilon$}2. The algorithms work by accelerating traditional interior point algorithms by quickly solving the system of linear equations that arises in each step. The contributions of this paper are twofold. First, we analyze the performance of interior point algorithms with approximate linear system solvers. This analysis alone provides an algorithm for the standard minimum cost flow problem that runs in time Om3/2 log U\vphantom\{\}--an improvement of roughly O\{n / m1/2\} over previous algorithms. Second, we examine the linear equations that arise when using an interior point algorithm to solve generalized flow problems. We observe that these belong to the family of symmetric M-matrices, and we then develop Om-time algorithms for solving linear systems in these matrices. These algorithms reduce the problem of solving a linear system in a symmetric M-matrix to that of solving O\{log n\} linear systems in symmetric diagonally-dominant matrices, which we can do in time Om using the algorithm of Spielman and Teng. All of our algorithms operate on numbers of bit length at most O\{log n U / {$\epsilon\rbrace$}.\vphantom\}},
  file = {/Users/rjkyng/Dropbox/Repos/papers/DS08.pdf},
  isbn = {978-1-60558-047-0},
  keywords = {approximation algorithms,interior-point algorithms,linear programming,network flows},
  series = {{{STOC}} '08}
}




@inproceedings{M13,
  title = {Navigating Central Path with Electrical Flows: {{From}} Flows to Matchings, and Back},
  shorttitle = {Navigating Central Path with Electrical Flows},
  booktitle = {2013 {{IEEE}} 54th {{Annual Symposium}} on {{Foundations}} of {{Computer Science}}},
  author = {Madry, Aleksander},
  year = {2013},
  pages = {253--262},
  publisher = {{IEEE}},
  file = {/Users/rjkyng/Zotero/storage/77XRU9CK/6686161.html}
}




@article{hs52,
  title={Methods of conjugate gradients for solving linear systems},
  author={Hestenes, Magnus R and Stiefel, Eduard and others},
  journal={Journal of research of the National Bureau of Standards},
  volume={49},
  number={6},
  pages={409--436},
  year={1952}
}


@article{l52,
  title={Solution of systems of linear equations by minimized iterations},
  author={Lanczos, Cornelius},
  journal={J. Res. Nat. Bur. Standards},
  volume={49},
  number={1},
  pages={33--53},
  year={1952}
}

@article{n83,
author="Nesterov, Y. E.",
title="A method for solving the convex programming problem with convergence rate $O(1/k^2)$",
journal="Dokl. Akad. Nauk SSSR",
ISSN="",
publisher="",
year="1983",
month="",
volume="269",
number="",
pages="543-547",
DOI="",
}


@article{ny83,
  title={Information-based complexity of mathematical programming},
  author={Nemirovski, A and Yudin, D},
  journal={Izvestia AN SSSR, Ser. Tekhnicheskaya Kibernetika (the journal is translated to English as Engineering Cybernetics. Soviet J. Computer \& Systems Sci.)},
  volume=1,
  year=1983
}


@article{do19,
  title={Conjugate gradients and accelerated methods unified: The approximate duality gap view},
  author={Diakonikolas, Jelena and Orecchia, Lorenzo},
  journal={arXiv preprint arXiv:1907.00289},
  year={2019}
}

@article{tropp15,
  title={An introduction to matrix concentration inequalities},
  author={Tropp, Joel A and others},
  journal={Foundations and Trends{\textregistered} in Machine Learning},
  volume={8},
  number={1-2},
  pages={1--230},
  year={2015},
  publisher={Now Publishers, Inc.}
}


@article{spielman2011graph,
  title={Graph sparsification by effective resistances},
  author={Spielman, Daniel A and Srivastava, Nikhil},
  journal={SIAM Journal on Computing},
  volume={40},
  number={6},
  pages={1913--1926},
  year={2011},
  publisher={SIAM}
}


@inproceedings{st04,
author = {Spielman, Daniel A. and Teng, Shang-Hua},
title = {Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems},
year = {2004},
isbn = {1581138520},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/1007352.1007372},
doi = {10.1145/1007352.1007372},
booktitle = {Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing},
pages = {81–90},
numpages = {10},
keywords = {graph partitioning, graph sparsification, preconditioners},
location = {Chicago, IL, USA},
series = {STOC ’04}
}


@INPROCEEDINGS{ks16, author={R. {Kyng} and S. {Sachdeva}}, booktitle={2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)}, title={Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple}, year={2016}, volume={}, number={}, pages={573-582},}


@article{tropp19,
  title={Matrix Concentration \& Computational Linear Algebra},
  author={Tropp, Joel A},
  year={2019},
}



@misc{S19,
  title = {Spectral and {{Algebraic Graph Theory}}},
  author = {Spielman, Daniel A},
  year = {2019},
  file = {/Users/rjkyng/Zotero/storage/DQHH5YWS/Spielman - Spectral and Algebraic Graph Theory.pdf},
  language = {en}
}


@article{BLLSSSW21,
  title = {Minimum {{Cost Flows}}, {{MDPs}}, and \$\$\textbackslash backslash\$ell\_1 \$-{{Regression}} in {{Nearly Linear Time}} for {{Dense Instances}}},
  author = {van den Brand, Jan and Lee, Yin Tat and Liu, Yang P. and Saranurak, Thatchaphol and Sidford, Aaron and Song, Zhao and Wang, Di},
  year = {2021},
  archiveprefix = {arXiv},
  eprint = {2101.05719},
  eprinttype = {arxiv},
  file = {/Users/rjkyng/Zotero/storage/GKJY3FQI/Brand et al. - 2021 - Minimum Cost Flows, MDPs, and $$backslash$ell_1 $.pdf;/Users/rjkyng/Zotero/storage/6APXSGMX/2101.html},
  journal = {arXiv preprint arXiv:2101.05719}
}

@article{GLP21,
  title = {Fully {{Dynamic Electrical Flows}}: {{Sparse Maxflow Faster Than Goldberg}}-{{Rao}}},
  shorttitle = {Fully {{Dynamic Electrical Flows}}},
  author = {Gao, Yu and Liu, Yang P. and Peng, Richard},
  year = {2021},
  month = jan,
  abstract = {We give an algorithm for computing exact maximum flows on graphs with \$m\$ edges and integer capacities in the range \$[1, U]\$ in \$\textbackslash widetilde\{O\}(m\^\{\textbackslash frac\{3\}\{2\} - \textbackslash frac\{1\}\{328\}\} \textbackslash log U)\$ time. For sparse graphs with polynomially bounded integer capacities, this is the first improvement over the \$\textbackslash widetilde\{O\}(m\^\{1.5\} \textbackslash log U)\$ time bound from [Goldberg-Rao JACM `98]. Our algorithm revolves around dynamically maintaining the augmenting electrical flows at the core of the interior point method based algorithm from [M\textbackslash k\{a\}dry JACM `16]. This entails designing data structures that, in limited settings, return edges with large electric energy in a graph undergoing resistance updates.},
  archiveprefix = {arXiv},
  eprint = {2101.07233},
  eprinttype = {arxiv},
  file = {/Users/rjkyng/Dropbox/Repos/papers/GLP21.pdf;/Users/rjkyng/Zotero/storage/7KC7MK3A/2101.html},
  journal = {arXiv:2101.07233 [cs]},
  keywords = {Computer Science - Data Structures and Algorithms},
  primaryclass = {cs}
}


@inproceedings{S17,
  title = {Area-Convexity, L{$\infty$} Regularization, and Undirected Multicommodity Flow},
  booktitle = {Proceedings of the 49th {{Annual ACM SIGACT Symposium}} on {{Theory}} of {{Computing}}},
  author = {Sherman, Jonah},
  year = {2017},
  pages = {452--460},
  file = {/Users/rjkyng/Dropbox/Repos/papers/S17.pdf;/Users/rjkyng/Zotero/storage/29TRDZRG/3055399.html}
}


@book{BV04,
  title = {Convex Optimization},
  author = {Boyd, Stephen and Vandenberghe, Lieven},
  year = {2004},
  publisher = {{Cambridge university press}},
  file = {/Users/rjkyng/Dropbox/Repos/papers/BBV04.pdf;/Users/rjkyng/Zotero/storage/3NTBIYQE/books.html}
}

@book{tarjan1983data,
  title={Data structures and network algorithms},
  author={Tarjan, Robert Endre},
  year={1983},
  publisher={SIAM}
}