Imagen de Portada

A Simple Average-case Analysis of Recursive Randomized Greedy MIS

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Dalirrooyfard, Mina, Makarychev, Konstantin, Mitrović, Slobodan
Formato:	Preprint
Publicado:	2026
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

Constraint Satisfaction Problems with Advice
por: Ghoshal, Suprovat, et al.
Publicado: (2024)

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

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

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
por: Ghoshal, Suprovat, et al.
Publicado: (2026)

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

Locally computing edge orientations
por: Mitrović, Slobodan, et al.
Publicado: (2025)

Graph Partitioning With Limited Moves
por: Behbahani, Majid, et al.
Publicado: (2024)

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

Approximation algorithms for satisfiable and nearly satisfiable ordering CSPs
por: Makarychev, Yury
Publicado: (2026)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
por: Dalirrooyfard, Mina, et al.
Publicado: (2023)

Optimal Phylogenetic Reconstruction from Sampled Quartets
por: Arvanitakis, Dionysis, et al.
Publicado: (2026)

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

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

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

Dynamic Algorithm for Explainable k-medians Clustering under lp Norm
por: Makarychev, Konstantin, et al.
Publicado: (2025)

A Unified Framework for Analysis of Randomized Greedy Matching Algorithms
por: Derakhshan, Mahsa, et al.
Publicado: (2026)

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

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

Simple Construction of Greedy Trees and Greedy Permutations
por: Chubet, Oliver, et al.
Publicado: (2024)

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

Hardness of Approximation for Shortest Path with Vector Costs
por: Carlson, Charlie, et al.
Publicado: (2025)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
por: Makarychev, Yury, et al.
Publicado: (2024)

Max-Cut with Multiple Cardinality Constraints
por: Makarychev, Yury, et al.
Publicado: (2025)

Greedy Dynamic Matching
por: Arnosti, Nick, et al.
Publicado: (2025)

New Greedy Spanners and Applications
por: Popova, Elizaveta, et al.
Publicado: (2026)

Singing a MIS
por: Irani, Sandy, et al.
Publicado: (2025)

Greedy BST on Permutation Initial Tree
por: Pareek, Akash
Publicado: (2024)

From Dynamic Programs to Greedy Algorithms
por: van Melkebeek, Dieter
Publicado: (2025)

A Lossless Deamortization for Dynamic Greedy Set Cover
por: Solomon, Shay, et al.
Publicado: (2024)

A Threshold Greedy Algorithm for Noisy Submodular Maximization
por: Chen, Wenjing, et al.
Publicado: (2023)

Engineering Algorithms for Dynamic Greedy Set Cover
por: Uzrad, Amitai
Publicado: (2026)

Greedy Completion for Weighted $(α,β)$-Spanners
por: Tzalik, Elad
Publicado: (2026)

An Improved Greedy Approximation for (Metric) $k$-Means
por: Charikar, Moses, et al.
Publicado: (2026)

Multiagent Matroid Upgrading: Greedy is Fair and Efficient
por: Ma, Qingwen, et al.
Publicado: (2026)

Graph Reconstruction via MIS Queries
por: Konrad, Christian, et al.
Publicado: (2024)

Maximum Coverage $k$-Antichains and Chains: A Greedy Approach
por: Cáceres, Manuel, et al.
Publicado: (2025)