Copertina

A framework for boosting matching approximation: parallel, distributed, and dynamic

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Mitrović, Slobodan, Sheu, Wen-Horng
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

Locally computing edge orientations
di: Mitrović, Slobodan, et al.
Pubblicazione: (2025)

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)

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

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

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

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

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

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

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

Differentially Private Gomory-Hu Trees
di: Aamand, Anders, et al.
Pubblicazione: (2024)

Simple parallel estimation of the partition ratio for Gibbs distributions
di: Harris, David G., et al.
Pubblicazione: (2025)

The adaptive complexity of parallelized log-concave sampling
di: Zhou, Huanjian, et al.
Pubblicazione: (2024)

Deterministic approximation for the volume of the truncated fractional matching polytope
di: Guo, Heng, et al.
Pubblicazione: (2024)

Improved parallel derandomization via finite automata with applications
di: Giliberti, Jeff, et al.
Pubblicazione: (2024)

Online matching on stochastic block model
di: Cherifa, Maria, et al.
Pubblicazione: (2025)

Suffix sorting via matching statistics
di: Lipták, Zsuzsanna, et al.
Pubblicazione: (2022)

Dynamic online matching with budget refills
di: Cherifa, Maria, et al.
Pubblicazione: (2024)

A customizable inexact subgraph matching algorithm for attributed graphs
di: Benko, Tatyana, et al.
Pubblicazione: (2025)

Graph matching based on similarities in structure and attributes
di: Candelier, Raphaël
Pubblicazione: (2024)

Online matching games in bipartite expanders and applications
di: Bauwens, Bruno, et al.
Pubblicazione: (2022)

Counting perfect matchings and Hamiltonian cycles faster
di: Li, Baitian
Pubblicazione: (2023)

Online matching with delays and stochastic arrival times
di: Mari, Mathieu, et al.
Pubblicazione: (2022)

Computing maximal palindromes in non-standard matching models
di: Mieno, Takuya, et al.
Pubblicazione: (2022)

Faster two-dimensional pattern matching with $k$ mismatches
di: Ellert, Jonas, et al.
Pubblicazione: (2024)

Efficient parameterized approximation
di: Kratsch, Stefan, et al.
Pubblicazione: (2025)

A simple $(2+ε)$-approximation for knapsack interdiction
di: Weninger, Noah
Pubblicazione: (2026)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
di: Bodlaender, Hans L., et al.
Pubblicazione: (2025)

Efficient terabyte-scale text compression via stable local consistency and parallel grammar processing
di: Diaz-Dominguez, Diego
Pubblicazione: (2024)

Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
di: Fan, Zhou, et al.
Pubblicazione: (2026)

New approximate distance oracles and their applications
di: Kadria, Avi, et al.
Pubblicazione: (2025)

Bicriteria approximation for $k$-edge-connectivity
di: Nutov, Zeev, et al.
Pubblicazione: (2025)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
di: Gawrychowski, Paweł, et al.
Pubblicazione: (2024)

Improved bicriteria approximation for $k$-edge-connectivity
di: Nutov, Zeev
Pubblicazione: (2025)

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

Beyond 2-approximation for k-Center in Graphs
di: Jin, Ce, et al.
Pubblicazione: (2025)