Cover Image

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fischer, Manuela, Mitrović, Slobodan, Uitto, Jara
Format:	Preprint
Published:	2021
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
by: Cambus, Mélanie, et al.
Published: (2022)

A $(4/3+\varepsilon)$-Approximation for Preemptive Scheduling with Batch Setup Times
by: Deppert, Max A., et al.
Published: (2025)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

Faster Semi-streaming Matchings via Alternating Trees
by: Mitrović, Slobodan, et al.
Published: (2024)

A $(2+\varepsilon)$-Approximation Algorithm for Metric $k$-Median
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
by: Ahmadi, Ali, et al.
Published: (2025)

A Tight ($3/2 + \varepsilon$)-Approximation Algorithm for Demand Strip Packing
by: Eberle, Franziska, et al.
Published: (2024)

Approximate counting of permutation patterns
by: Ben-Eliezer, Omri, et al.
Published: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
by: Mitrović, Slobodan, et al.
Published: (2025)

A Simpler Analysis for $\varepsilon$-Clairvoyant Flow Time Scheduling
by: Gupta, Anupam, et al.
Published: (2026)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
by: Łącki, Jakub, et al.
Published: (2025)

A dynamic $(1+\varepsilon)$-spanner for disk intersection graphs
by: de Berg, Sarita, et al.
Published: (2026)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
by: Dalirrooyfard, Mina, et al.
Published: (2024)

A framework for boosting matching approximation: parallel, distributed, and dynamic
by: Mitrović, Slobodan, et al.
Published: (2025)

Efficient $\varepsilon$-approximate minimum-entropy couplings
by: Compton, Spencer
Published: (2025)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
by: Assadi, Sepehr
Published: (2023)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
by: Dalirrooyfard, Mina, et al.
Published: (2026)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
by: Dalirrooyfard, Mina, et al.
Published: (2025)

Locally computing edge orientations
by: Mitrović, Slobodan, et al.
Published: (2025)

Bounding $\varepsilon$-scatter dimension via metric sparsity
by: Bourneuf, Romain, et al.
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Beyond Brooks: $(Δ-1)$-Coloring in Semi-Streaming
by: Flin, Maxime, et al.
Published: (2026)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
by: Mitrović, Slobodan, et al.
Published: (2026)

Semi-Streaming Algorithms for Hypergraph Matching
by: Reinstädtler, Henrik, et al.
Published: (2025)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
by: Veldt, Nate
Published: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
by: Azarmehr, Amir, et al.
Published: (2025)

Semi-Robust Communication Complexity of Maximum Matching
by: Huete, Gabriel Cipriani, et al.
Published: (2025)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
by: Mahabadi, Sepideh, et al.
Published: (2025)

Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
by: Dhulipala, Laxman, et al.
Published: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

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

Infinitely Divisible Noise for Differential Privacy: Nearly Optimal Error in the High $\varepsilon$ Regime
by: Harrison, Charlie, et al.
Published: (2025)

Dynamic PageRank: Algorithms and Lower Bounds
by: Jayaram, Rajesh, et al.
Published: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
by: Alipour, Sharareh, et al.
Published: (2025)

Near-Optimal Distributed Ruling Sets for Trees and High-Girth Graphs
by: Baumecker, Malte, et al.
Published: (2025)

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

Dynamic Construction of the Lovász Local Lemma
by: Haeupler, Bernhard, et al.
Published: (2026)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
by: Aamand, Anders, et al.
Published: (2025)