5 papers
Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications
Slobodan Mitrović, Theodore Pan, Wen-Horng Sheu
A number of fundamental graph problems admit simple algorithms based on iterative peeling: repeatedly remove all vertices whose current degree is below a fixed threshold. This para…
Dynamic Construction of the Lovász Local Lemma
Bernhard Haeupler, Slobodan Mitrović, Srikkanth Ramachandran +2
This paper proves that a wide class of local search algorithms extend as is to the fully dynamic setting with an adaptive adversary, achieving an amortized number of…
Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
Jakub Łącki, Slobodan Mitrović, Srikkanth Ramachandran +1
We study the allocation problem in the Massively Parallel Computation (MPC) model. This problem is a special case of -matching, in which the input is a bipartite graph with capa…
A framework for boosting matching approximation: parallel, distributed, and dynamic
Slobodan Mitrović, Wen-Horng Sheu
This work designs a framework for boosting the approximation guarantee of maximum matching algorithms. As input, the framework receives a parameter and an oracle access to a…
Faster Semi-streaming Matchings via Alternating Trees
Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski +1
We design a deterministic algorithm for the -approximate maximum matching problem. Our primary result demonstrates that this problem can be solved in semi-stream…