Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available January 1, 2025

Free, publiclyaccessible full text available November 6, 2024

We give an algorithm that computes exact maximum flows and minimumcost flows on directed graphs with m edges and polynomially bounded integral demands, costs, and capacities in m^{1+o(1)} time. Our algorithm builds the flow through a sequence of m^{1+o(1)} approximate undirected minimumratio cycles, each of which is computed and processed in amortized m^{o(1)} time using a new dynamic graph data structure. Our framework extends to algorithms running in m^{1+o(1)} time for computing flows that minimize general edgeseparable convex functions to high accuracy. This gives almostlinear time algorithms for several problems including entropyregularized optimal transport, matrix scaling, pnorm flows, and pnorm isotonic regression on arbitrary directed acyclic graphs.more » « less

We present an algorithm that, with high probability, generates a random spanning tree from an edgeweighted undirected graph in \Otil(n^{5/3 }m^{1/3}) time\footnote{The \Otil(\cdot) notation hides \poly(\log n) factors}. The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(n^\omega). For the special case of unweighted graphs, this improves upon the best previously known running time of \tilde{O}(\min\{n^{\omega},m\sqrt{n},m^{4/3}\}) for m >> n^{7/4} (Colbourn et al. '96, KelnerMadry '09, Madry et al. '15). The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinantbased and random walkbased techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement). As part of our algorithm, we show how to compute \epsapproximate effective resistances for a set SS of vertex pairs via approximate Schur complements in \Otil(m+(n + S)\eps^{2}) time, without using the JohnsonLindenstrauss lemma which requires \Otil( \min\{(m + S)\eps^{2}, m+n\eps^{4} +S\eps^{2}\}) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn't sufficiently accurate.more » « less