4 papers
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…
Approximate counting of permutation patterns
Omri Ben-Eliezer, Slobodan Mitrović, Pranjal Srivastava
We consider the problem of counting the copies of a length- pattern in a sequence , where a copy is a subset of indices $i_1 < \ldots < i_k \in…