4 papers
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…
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…