Image de couverture de livre

On Thin Perfect Matchings up to Polylogarithmic Factors

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Haqi, Alireza, Gharan, Shayan Oveis
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
par: Gharan, Shayan Oveis, et autres
Publié: (2025)

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
par: Leake, Jonathan, et autres
Publié: (2025)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
par: Kocurek, Nicholas, et autres
Publié: (2026)

On approximability of the Permanent of PSD matrices
par: Ebrahimnejad, Farzam, et autres
Publié: (2024)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
par: Leake, Jonathan, et autres
Publié: (2025)

Constant-Stretch Rounding on the Hypersimplex
par: Anari, Nima, et autres
Publié: (2026)

Perfect $L_p$ Sampling with Polylogarithmic Update Time
par: Swartworth, William, et autres
Publié: (2025)

Fast Spanning Tree Sampling in Broadcast Congested Clique
par: Anari, Nima, et autres
Publié: (2026)

A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
par: Dufay, Marc, et autres
Publié: (2025)

Memory Reallocation with Polylogarithmic Overhead
par: Jin, Ce
Publié: (2026)

Polylogarithmic Approximation for Robust s-t Path
par: Li, Shi, et autres
Publié: (2023)

Dynamic Longest Common Substring in Polylogarithmic Time
par: Charalampopoulos, Panagiotis, et autres
Publié: (2020)

Improving Order with Queues
par: Karrenbauer, Andreas, et autres
Publié: (2022)

Perfect Matchings and Popularity in the Many-to-Many Setting
par: Kavitha, Telikepalli, et autres
Publié: (2024)

On Finding $\ell$-th Smallest Perfect Matchings
par: Maalouly, Nicolas El, et autres
Publié: (2025)

On the Complexity of the Odd-Red Bipartite Perfect Matching Polytope
par: Nägele, Martin, et autres
Publié: (2026)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
par: Kalavas, Andreas, et autres
Publié: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
par: Kalavas, Andreas, et autres
Publié: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
par: Meierhans, Simon, et autres
Publié: (2025)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
par: Chekuri, Chandra, et autres
Publié: (2024)

Finding Spanning Trees with Perfect Matchings
par: Bérczi, Kristóf, et autres
Publié: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
par: Agarwal, Arpit, et autres
Publié: (2024)

Parallel Small Vertex Connectivity in Near-Linear Work and Polylogarithmic Depth
par: Jiang, Yonggang, et autres
Publié: (2025)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
par: Arkhipov, Pavel, et autres
Publié: (2026)

Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
par: Koh, Zhuan Khye, et autres
Publié: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
par: Anand, Aditya, et autres
Publié: (2025)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
par: Hua, Kevin, et autres
Publié: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
par: Bucić, Matija, et autres
Publié: (2025)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
par: Hathcock, Daniel, et autres
Publié: (2025)

Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
par: Ansaripour, Matin, et autres
Publié: (2024)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
par: Maalouly, Nicolas El, et autres
Publié: (2025)

Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space
par: Lebeda, Christian Janos, et autres
Publié: (2024)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
par: Braverman, Vladimir, et autres
Publié: (2024)

Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
par: Bhore, Sujoy, et autres
Publié: (2023)

Polylogarithmic Approximation for Covering and Connecting Multi-Interface Networks
par: Szyfelbein, Michał, et autres
Publié: (2026)

A Single-Sample Polylogarithmic Regret Bound for Nonstationary Online Linear Programming
par: Xu, Haoran, et autres
Publié: (2026)

Engineering Minimal k-Perfect Hash Functions
par: Hermann, Stefan, et autres
Publié: (2025)

Modern Minimal Perfect Hashing: A Survey
par: Lehmann, Hans-Peter, et autres
Publié: (2025)

On recognizing graphs representing Persistent Perfect Phylogenies
par: Bonizzoni, Paola, et autres
Publié: (2025)