Cover Image

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Agarwal, Arpit, Khanna, Sanjeev, Li, Huan, Patil, Prathamesh, Wang, Chen, White, Nathan, Zhong, Peilin
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
by: Jiang, Yonggang, et al.
Published: (2025)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
by: Koh, Zhuan Khye, et al.
Published: (2024)

Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Misalignment, Learning, and Ranking: Harnessing Users Limited Attention
by: Agarwal, Arpit, et al.
Published: (2024)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
by: Brand, Jan van den, et al.
Published: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Polylogarithmic Approximation for Robust s-t Path
by: Li, Shi, et al.
Published: (2023)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
by: Chuzhoy, Julia, et al.
Published: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
by: Hua, Kevin, et al.
Published: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
by: Haeupler, Bernhard, et al.
Published: (2025)

On the Parallel Complexity of Finding a Matroid Basis
by: Khanna, Sanjeev, et al.
Published: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
by: Braverman, Vladimir, et al.
Published: (2024)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
by: Chekuri, Chandra, et al.
Published: (2024)

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
by: Grunau, Christoph, et al.
Published: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
by: Khanna, Sanjeev, et al.
Published: (2025)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

Learning-Augmented Dynamic Submodular Maximization
by: Agarwal, Arpit, et al.
Published: (2023)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
by: Khanna, Sanjeev, et al.
Published: (2026)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

Query Complexity of the Metric Steiner Tree Problem
by: Chen, Yu, et al.
Published: (2022)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
by: Anand, Aditya, et al.
Published: (2025)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

Memory Reallocation with Polylogarithmic Overhead
by: Jin, Ce
Published: (2026)

A Theory of Spectral CSP Sparsification
by: Khanna, Sanjeev, et al.
Published: (2025)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
by: Khanna, Sanjeev, et al.
Published: (2025)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
by: Assadi, Sepehr, et al.
Published: (2025)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
by: Assadi, Sepehr, et al.
Published: (2024)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
by: Khanna, Sanjeev, et al.
Published: (2026)

A Faster Deterministic Algorithm for Fully Dynamic Maximal Matching
by: Chuzhoy, Julia, et al.
Published: (2026)

Streaming Maximal Matching with Bounded Deletions
by: Khanna, Sanjeev, et al.
Published: (2025)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Learning-augmented Maximum Independent Set
by: Braverman, Vladimir, et al.
Published: (2024)

High-Dimensional Geometric Streaming for Nearly Low Rank Data
by: Esfandiari, Hossein, et al.
Published: (2024)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

On Thin Perfect Matchings up to Polylogarithmic Factors
by: Haqi, Alireza, et al.
Published: (2026)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
by: Henzinger, Monika, et al.
Published: (2025)