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…
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…
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…
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-stre…