# Coordinate Methods for Accelerating $\ell_\infty$ Regression and Faster Approximate Maximum Flow

Preprint · Aaron Sidford, Kevin Tian

- Archive id: arxiv:1808.01278
- Published: 2018-08-03
- arXiv: https://arxiv.org/abs/1808.01278
- Source URL: https://arxiv.org/abs/1808.01278
- PDF: https://arxiv.org/pdf/1808.01278
- Provenance: arxiv

## Abstract

We provide faster algorithms for approximately solving $\\ell\_{\\infty}$ regression, a fundamental problem prevalent in both combinatorial and continuous optimization. In particular, we provide accelerated coordinate descent methods capable of provably exploiting dynamic measures of coordinate smoothness, and apply them to $\\ell\_\\infty$ regression over a box to give algorithms which converge in $k$ iterations at a $O(1/k)$ rate. Our algorithms can be viewed as an alternative approach to the recent breakthrough result of Sherman \[She17\] which achieves a similar runtime improvement over classic algorithmic approaches, i.e. smoothing and gradient descent, which either converge at a $O(1/\\sqrt{k})$ rate or have running times with a worse dependence on problem parameters. Our runtimes match those of \[She17\] across a broad range of parameters and achieve improvement in certain structured cases. We demonstrate the efficacy of our result by providing faster algorithms for the well-studied maximum flow problem. Directly leveraging our accelerated $\\ell\_\\infty$ regression algorithms imply a $\\tilde{O}\\left(m + \\sqrt{mn}/ε\\right)$ runtime to compute an $ε$-approximate maximum flow for an undirected graph with $m$ edges and $n$ vertices, generically improving upon the previous best known runtime of $\\tilde{O}\\left(m/ε\\right)$ in \[She17\] whenever the graph is slightly dense. We further design an algorithm adapted to the structure of the regression problem induced by maximum flow obtaining a runtime of $\\tilde{O}\\left(m + \\max(n, \\sqrt{ns})/ε\\right)$, where $s$ is the squared $\\ell\_2$ norm of the congestion of any optimal flow. Moreover, we show how to leverage this result to achieve improved exact algorithms for maximum flow on a variety of unit capacity graphs. We hope that our work serves as an important step towards achieving even faster maximum flow algorithms.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.