Faster High Accuracy Multi-Commodity Flows via Graph Techniques

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=unf92kJuZ8A


Duration: 45:26
283 views
9

Jan van der Brand (KTH Royal Institute of Technology)
https://simons.berkeley.edu/talks/jan-van-der-brand-kth-royal-institute-technology-2023-09-21
Dynamic Graphs and Algorithm Design

In this talk, we will see that graph techniques can speed up algorithms for solving multi-commodity flow to high accuracy. This is unexpected as it was shown in [Ita'79 and Ding-Kyng-Zhang'22] that general linear programs without any graph structure can be reduced to multi-commodity flows.

In addition to outlining our improved multi-commodity flow algorithm, we will see open problems and bottlenecks for improving general linear program solvers and how they connect to graph problems.



Other Videos By Simons Institute for the Theory of Computing


2023-09-27Massively Parallel Evaluation of Relational Queries II
2023-09-27Massively Parallel Evaluation of Relational Queries I
2023-09-26Intermediate Relational Algorithm Design
2023-09-26Introduction to Relational Algorithms
2023-09-25Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: I
2023-09-25Fine Grained Complexity
2023-09-25Accessing Answers to Unions of Conjunctive Queries with Ideal Time Guarantees: II
2023-09-22Accelerating the Multiplicative-Weights Framework for Graph Linear Programs
2023-09-22Parallel Batch-Dynamic Graph Algorithms
2023-09-22Recent Progress on Sublinear Time Algorithms for Maximum Matching: Lower Bounds
2023-09-21Faster High Accuracy Multi-Commodity Flows via Graph Techniques
2023-09-21Minimum Isolating Cuts: A New Tool for Solving Minimum Cut Problems
2023-09-21On Dynamic Graph Approximations: The case of j-Trees
2023-09-21On Engineering Dynamic Graph Algorithms
2023-09-21Dynamic Graphs on the GPU
2023-09-20Dynamic PageRank: Additive Error and Batch Recomputation
2023-09-20Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
2023-09-20Online List Labeling: Breaking the log^2 n Barrier
2023-09-20Practical Dynamic Graph Algorithms: Data Structures and Connections Between Models
2023-09-20Decremental Shortest Paths against an Adaptive Adversary
2023-09-19Dynamic Matching: Rounding & Sparsification (And New Tools)


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Dynamic Graphs and Algorithm Design
Jan van der Brand