Buchumschlag

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Łącki, Jakub, Mitrović, Slobodan, Ramachandran, Srikkanth, Sheu, Wen-Horng
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Dynamic Construction of the Lovász Local Lemma
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

A framework for boosting matching approximation: parallel, distributed, and dynamic
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2025)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2026)

Faster Semi-streaming Matchings via Alternating Trees
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
von: Dhulipala, Laxman, et al.
Veröffentlicht: (2024)

Approximate counting of permutation patterns
von: Ben-Eliezer, Omri, et al.
Veröffentlicht: (2024)

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

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2024)

New Parallel and Streaming Algorithms for Directed Densest Subgraph
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2025)

DynHAC: Fully Dynamic Approximate Hierarchical Agglomerative Clustering
von: Yu, Shangdi, et al.
Veröffentlicht: (2025)

SPARSE-PIVOT: Dynamic correlation clustering for node insertions
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2025)

Locally computing edge orientations
von: Mitrović, Slobodan, et al.
Veröffentlicht: (2025)

A Simple Average-case Analysis of Recursive Randomized Greedy MIS
von: Dalirrooyfard, Mina, et al.
Veröffentlicht: (2026)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

Faster Algorithms for Longest Common Substring
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2021)

Faster Algorithms for Graph Monopolarity
von: Philip, Geevarghese, et al.
Veröffentlicht: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
von: Kacham, Praneeth, et al.
Veröffentlicht: (2024)

Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search
von: Gottesbüren, Lars, et al.
Veröffentlicht: (2024)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
von: Manoharan, Vignesh, et al.
Veröffentlicht: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
von: Filtser, Arnold, et al.
Veröffentlicht: (2025)

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

BYO: A Unified Framework for Benchmarking Large-Scale Graph Containers
von: Wheatman, Brian, et al.
Veröffentlicht: (2024)

A Faster Deterministic Approximation Algorithm for TTP-2
von: Kanaya, Yuga, et al.
Veröffentlicht: (2023)

Approximation Algorithms for Network Design in Non-Uniform Fault Models
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
von: Jin, Ce, et al.
Veröffentlicht: (2024)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
von: Dong, Sally, et al.
Veröffentlicht: (2023)

Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
von: Kwok, Shawxing
Veröffentlicht: (2025)

Faster Approximate Linear Matroid Intersection
von: Terao, Tatsuya
Veröffentlicht: (2026)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Simple and Faster Algorithms for Knapsack
von: He, Qizheng, et al.
Veröffentlicht: (2023)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
von: Mallek, Nadym, et al.
Veröffentlicht: (2025)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

Faster Combinatorial k-Clique Algorithms
von: Abboud, Amir, et al.
Veröffentlicht: (2024)

Faster Weak Expander Decompositions and Approximate Max Flow
von: Fleischmann, Henry, et al.
Veröffentlicht: (2025)

Faster Approximate Fixed Points of $\ell_\infty$-Contractions
von: Feodorov, Andrei, et al.
Veröffentlicht: (2026)

Faster CONGEST Approximation Algorithms for Maximum Weighted Independent Set in Sparse Graphs
von: Faour, Salwa, et al.
Veröffentlicht: (2025)

An Approximation Algorithm for Monotone Submodular Cost Allocation
von: Mizutani, Ryuhei
Veröffentlicht: (2025)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
von: Zhao, Jingyang, et al.
Veröffentlicht: (2025)