Cover Image

Matching Composition and Efficient Weight Reduction in Dynamic Matching

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bernstein, Aaron, Chen, Jiale, Dudeja, Aditi, Langley, Zachary, Sidford, Aaron, Tu, Ta-Wei
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

Entropy Regularization and Faster Decremental Matching in General Graphs
by: Chen, Jiale, et al.
Published: (2023)

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

A Note on Rounding Matchings in General Graphs
by: Dudeja, Aditi
Published: (2024)

A Weighted-to-Unweighted Reduction for Matroid Intersection
by: Dudeja, Aditi, et al.
Published: (2026)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
by: Bhattacharya, Sayan, et al.
Published: (2023)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
by: Bernstein, Aaron, et al.
Published: (2025)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
by: Bernstein, Aaron, et al.
Published: (2024)

Reusing Samples in Variance Reduction
by: Jin, Yujia, et al.
Published: (2025)

Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
by: Chen, Li, et al.
Published: (2025)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

Quantum speedups for stochastic optimization
by: Sidford, Aaron, et al.
Published: (2023)

On computing approximate Lewis weights
by: Apers, Simon, et al.
Published: (2024)

Sparse Submodular Function Minimization
by: Graur, Andrei, et al.
Published: (2023)

Stability of the Lanczos Method for Matrix Function Approximation
by: Musco, Cameron, et al.
Published: (2017)

Closing the Gap Between Directed Hopsets and Shortcut Sets
by: Bernstein, Aaron, et al.
Published: (2022)

Efficient Matroid Intersection via a Batch-Update Auction Algorithm
by: Blikstad, Joakim, et al.
Published: (2024)

Eulerian Graph Sparsification by Effective Resistance Decomposition
by: Jambulapati, Arun, et al.
Published: (2024)

From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
by: Dadush, Daniel, et al.
Published: (2025)

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

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

Improved girth approximation in weighted undirected graphs
by: Kadria, Avi, et al.
Published: (2025)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
by: Khoury, Seri, et al.
Published: (2025)

Convex optimization with $p$-norm oracles
by: Adil, Deeksha, et al.
Published: (2024)

Balancing Gradient and Hessian Queries in Non-Convex Optimization
by: Adil, Deeksha, et al.
Published: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
by: Dereziński, Michał, et al.
Published: (2025)

Pattern Matching under Weighted Edit Distance
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Greedy Dynamic Matching
by: Arnosti, Nick, et al.
Published: (2025)

Closing the Computational-Query Depth Gap in Parallel Stochastic Convex Optimization
by: Jambulapati, Arun, et al.
Published: (2024)

Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
by: Bernstein, Aaron, et al.
Published: (2025)

A PTAS for Weighted Triangle-free 2-Matching
by: Bosch-Calvo, Miguel, et al.
Published: (2026)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
by: Ferdous, S M, et al.
Published: (2023)

Extracting Dual Solutions via Primal Optimizers
by: Carmon, Yair, et al.
Published: (2024)

Isotropic Noise in Stochastic and Quantum Convex Optimization
by: Marsden, Annie, et al.
Published: (2025)