 Award ID(s):
 1718342
 NSFPAR ID:
 10204854
 Date Published:
 Journal Name:
 IEEE Symposium on Foundations of Computer Science
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

null (Ed.)We present an $m^{4/3}+o(1) \log W$ time algorithm for solving the minimum cost flow problem in graphs with unit capacity, where W is the maximum absolute value of any edge weight. For sparse graphs, this improves over the best known running time for this problem and, by wellknown reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite $b$matching when $\b\_1 = O(m)$, and recovers the running time of the currently fastest algorithm for maximum flow in graphs with unit capacities (LiuSidford, 2020). Our algorithm relies on developing an interior point method–based framework which acts on the space of circulations in the underlying graph. From the combinatorial point of view, this framework can be viewed as iteratively improving the cost of a suboptimal solution by pushing flow around circulations. These circulations are derived by computing a regularized version of the standard Newton step, which is partially inspired by previous work on the unitcapacity maximum flow problem (LiuSidford, 2019), and subsequently refined based on the very re cent progress on this problem (LiuSidford, 2020). The resulting step problem can then be computed efficiently using the recent work on $l_p$norm minimizing flows (KyngPengSachdeva Wang, 2019). We obtain our faster algorithm by combining this new step primitive with a customized preconditioning method, which aims to ensure that the graph on which these circulations are computed has sufficiently large conductance.more » « less

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

null (Ed.)We present an $\tilde O(m+n^{1.5})$time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negativeweight shortest paths, and optimal transport) on $m$edge, $n$node graphs. For maximum cardinality bipartite matching on moderately dense graphs, i.e. $m = \Omega(n^{1.5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(m\sqrt{n})$time [Dinic 1970; HopcroftKarp 1971; Karzanov 1973] and $\tilde O(n^\omega)$time algorithms [IbarraMoran 1981] (where currently $\omega\approx 2.373$). On sparser graphs, i.e. when $m = n^{9/8 + \delta}$ for any constant $\delta>0$, our result improves upon the recent advances of [Madry 2013] and [LiuSidford 2020b, 2020a] which achieve an $\tilde O(m^{4/3+o(1)})$ runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v.d.BrandLeeSidfordSong 2020], providing a general primaldual IPM framework and new samplingbased techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublineartime algorithm for detecting and sampling highenergy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v.d.Brand~et~al.] and our new IPMs. Combining this general machinery yields a simpler $\tilde O(n \sqrt{m})$ time algorithm for matching based on the logarithmic barrier function, and our stateoftheart $\tilde O(m+n^{1.5})$ time algorithm for matching based on the [LeeSidford 2014] barrier (as regularized in [v.d.Brand~et~al.]).more » « less

Minimum flow decomposition (MFD) is the NPhard problem of finding a smallest decomposition of a network flow/circulation
X on a directed graphG into weighted sourcetosink paths whose weighted sum equalsX . We show that, for acyclic graphs, considering thewidth of the graph (the minimum number of paths needed to cover all of its edges) yields advances in our understanding of its approximability. For the version of the problem that uses only nonnegative weights, we identify and characterise a new class ofwidthstable graphs, for which a popular heuristic is aO (logVal (X ))approximation (Val (X ) being the total flow ofX ), and strengthen its worstcase approximation ratio from to Ω (\(\Omega (\sqrt {m})\) m /logm ) for sparse graphs, wherem is the number of edges in the graph. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a (⌈ log ‖ X ‖ ⌉ +1)approximation (‖X ‖ being the maximum absolute value ofX on any edge) using a poweroftwo approach, combined with parity fixing arguments and a decomposition of unitary circulations (‖X ‖ ≤ 1), using a generalised notion of width for this problem. Finally, we disprove a conjecture about the linear independence of minimum (nonnegative) flow decompositions posed by Kloster et al. [2018 ], but show that its useful implication (polynomialtime assignments of weights to a given set of paths to decompose a flow) holds for the negative version. 
We give an algorithm to find a minimum cut in an edgeweighted directed graph with n vertices and m edges in O ̃(n · max{m^{2/3}, n}) time. This improves on the 30 year old bound of O ̃(nm) obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain O ̃ (n^2 /ε^2 )time (1+ε)approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed ε. Before our work, no (1+ε)approximation algorithm better than the exact runtime of O ̃(nm) is known for either problem. Our algorithms follow a twostep template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to O ̃ (min{n/m^{1/3} , √n}) calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.more » « less