Buchumschlag

Streaming and Communication Complexity of Load-Balancing via Matching Contractors

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Assadi, Sepehr, Bernstein, Aaron, Langley, Zachary, Lau, Lap Chi, Wang, Robert
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
von: Assadi, Sepehr
Veröffentlicht: (2023)

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Matching Composition and Efficient Weight Reduction in Dynamic Matching
von: Bernstein, Aaron, et al.
Veröffentlicht: (2024)

Faster Vizing and Near-Vizing Edge Coloring Algorithms
von: Assadi, Sepehr
Veröffentlicht: (2024)

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
von: Assadi, Sepehr, et al.
Veröffentlicht: (2023)

Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
von: Assadi, Sepehr, et al.
Veröffentlicht: (2022)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2026)

Coloring Graphs with Few Colors in the Streaming Model
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Spectral Sparsification by Deterministic Discrepancy Walk
von: Lau, Lap Chi, et al.
Veröffentlicht: (2024)

Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

A Combinatorial Characterization of Constant Mixing Time
von: Lau, Lap Chi, et al.
Veröffentlicht: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Experimental Design Using Interlacing Polynomials
von: Lau, Lap Chi, et al.
Veröffentlicht: (2024)

From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

On the Houdré-Tetali conjecture about an isoperimetric constant of graphs
von: Lau, Lap Chi, et al.
Veröffentlicht: (2024)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Distributed Triangle Detection is Hard in Few Rounds
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Weighted Matching in the Random-Order Streaming and Robust Communication Models
von: Hashemi, Diba, et al.
Veröffentlicht: (2024)

Closing the Gap Between Directed Hopsets and Shortcut Sets
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

Semi-Robust Communication Complexity of Maximum Matching
von: Huete, Gabriel Cipriani, et al.
Veröffentlicht: (2025)

The Communication Complexity of Pattern Matching with Edits Revisited
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2026)

Load Balancing with Duration Predictions
von: Azar, Yossi, et al.
Veröffentlicht: (2025)

History-Independent Load Balancing
von: Bender, Michael A., et al.
Veröffentlicht: (2026)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

Are there graphs whose shortest path structure requires large edge weights?
von: Bernstein, Aaron, et al.
Veröffentlicht: (2023)

Semi-Streaming Algorithms for Hypergraph Matching
von: Reinstädtler, Henrik, et al.
Veröffentlicht: (2025)

Streaming Maximal Matching with Bounded Deletions
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Improved Online Load Balancing in the Two-Norm
von: Borst, Sander, et al.
Veröffentlicht: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

On the Streaming Complexity of Expander Decomposition
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
von: Ferdous, S M, et al.
Veröffentlicht: (2023)

On the Communication Complexity of Approximate Pattern Matching
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2024)