 Award ID(s):
 1718342
 NSFPAR ID:
 10206560
 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 bmatching 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 recent progress on this problem (LiuSidford, 2020). The resulting step problem can then be computed efficiently using the recent work on l_pnorm minimizing flows (KyngPengSachdevaWang, 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

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

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

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. 
Tauman Kalai, Yael (Ed.)Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, nearlinear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a nearlinear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vectormatrixvector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cuttoggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cuttoggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cuttoggling algorithm can achieve (almost) the same running time as its primal cycletoggling counterpart.more » « less