Copertina

Approximating Maximum Matching Requires Almost Quadratic Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Behnezhad, Soheil, Roghani, Mohammad, Rubinstein, Aviad
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Sublinear Algorithms for TSP via Path Covers
di: Behnezhad, Soheil, et al.
Pubblicazione: (2023)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
di: Azarmehr, Amir, et al.
Pubblicazione: (2024)

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

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

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
di: Mao, Xiao, et al.
Pubblicazione: (2026)

Vizing's Theorem in Deterministic Almost-Linear Time
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Stochastic Matching via In-n-Out Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2024)

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

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Single-Pass Streaming CSPs via Two-Tier Sampling
di: Azarmehr, Amir, et al.
Pubblicazione: (2026)

Improved Approximation for Ranking on General Graphs
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2025)

Lower Bounds for Non-adaptive Local Computation Algorithms
di: Azarmehr, Amir, et al.
Pubblicazione: (2025)

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
di: Rubinstein, Aviad
Pubblicazione: (2016)

Vizing's Theorem in Near-Linear Time
di: Assadi, Sepehr, et al.
Pubblicazione: (2024)

Stochastic Matching via Local Sparsification
di: Ahmadian, Sara, et al.
Pubblicazione: (2026)

Markov Chains with Rewinding
di: Azarmehr, Amir, et al.
Pubblicazione: (2026)

Correlation Clustering Beyond the Pivot Algorithm
di: Behnezhad, Soheil, et al.
Pubblicazione: (2024)

Approximating Directed Connectivity in Almost-Linear Time
di: Quanrud, Kent
Pubblicazione: (2025)

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

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
di: Rubinstein, Aviad, et al.
Pubblicazione: (2026)

A Simple Analysis of Ranking in General Graphs
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2025)

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

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
di: Mao, Xiao
Pubblicazione: (2023)

Approximate Counting for Spin Systems in Sub-Quadratic Time
di: Anand, Konrad, et al.
Pubblicazione: (2023)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
di: Mahabadi, Sepideh, et al.
Pubblicazione: (2024)

Sublinear Metric Steiner Forest via Maximal Independent Set
di: Mahabadi, Sepideh, et al.
Pubblicazione: (2025)

Stable Matching with Interviews
di: Ashlagi, Itai, et al.
Pubblicazione: (2025)

Distributed Approximate Maximum Matching and Minimum Vertex Cover via Generalized Graph Decomposition
di: Davies-Peck, Peter
Pubblicazione: (2026)

Strategizing against No-Regret Learners in First-Price Auctions
di: Rubinstein, Aviad, et al.
Pubblicazione: (2024)

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments
di: Bai, Tian
Pubblicazione: (2025)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
di: Bucić, Matija, et al.
Pubblicazione: (2025)

Almost Tight Bounds for Online Hypergraph Matching
di: Tröbst, Thorben, et al.
Pubblicazione: (2024)

An Improved Kernel and Parameterized Algorithm for Almost Induced Matching
di: Liu, Yuxi, et al.
Pubblicazione: (2023)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
di: Das, Rathish, et al.
Pubblicazione: (2025)

Optimal Single-Choice Prophet Inequalities from Samples
di: Rubinstein, Aviad, et al.
Pubblicazione: (2019)

FPT Approximations for Connected Maximum Coverage
di: Inamdar, Tanmay, et al.
Pubblicazione: (2026)

Parallel Sampling via Counting
di: Anari, Nima, et al.
Pubblicazione: (2024)

Deterministic $(1+\varepsilon)$-Approximate Maximum Matching with $\mathsf{poly}(1/\varepsilon)$ Passes in the Semi-Streaming Model and Beyond
di: Fischer, Manuela, et al.
Pubblicazione: (2021)