Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs

DOI10.1145/1993636.1993674zbMath1288.94127arXiv1010.2921OpenAlexW2153441719MaRDI QIDQ5419097

Jonathan A. Kelner, Aleksander Mądry, Paul Christiano, Shang-Hua Teng, Daniel A. Spielman

Publication date: 5 June 2014

Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1010.2921

zbMATH Keywords

maximum flows minimum cuts multiplicative weights update method electrical flows Laplacian linear systems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10) Applications of graph theory to circuits and networks (94C15) Approximation algorithms (68W25) Flows in graphs (05C21)

Related Items (38)

A polynomial algorithm for deciding the validity of an electrical distribution tree ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Flow-Based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance ⋮ Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Optimization with Non-Differentiable Constraints with Applications to Fairness, Recall, Churn, and Other Goals ⋮ Deciding probabilistic automata weak bisimulation: theory and practice ⋮ Quadratically Regularized Optimal Transport on Graphs ⋮ Status determination by interior-point methods for convex optimization problems in domain-driven form ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration ⋮ A Spectral Approach to Network Design ⋮ On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Unnamed Item ⋮ Numerical Methods for Gremban's Expansion of Signed Graphs ⋮ Graph Clustering using Effective Resistance ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ A queueing network-based distributed Laplacian solver for directed graphs ⋮ Efficient Convex Optimization with Oracles ⋮ Optimisation of electrical network configuration: complexity and algorithms for ring topologies ⋮ Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ A queueing network-based distributed Laplacian solver ⋮ Lower bounds for in-network computation of arbitrary functions ⋮ On graph parameters guaranteeing fast sandpile diffusion ⋮ A Laplacian approach to $\ell_1$-norm minimization ⋮ Unnamed Item ⋮ Exact and approximation algorithms for weighted matroid intersection ⋮ Random Walks, Electric Networks and The Transience Class problem of Sandpiles ⋮ Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ Electrical flows over spanning trees ⋮ Unnamed Item ⋮ Near-Optimal Distributed Maximum Flow

This page was built for publication: Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs