32 citations · 47 across the 7 of their papers we have counts for
10 papers
Massively Parallel Algorithms for -Matching
Mohsen Ghaffari, Christoph Grunau, Slobodan Mitrović
This paper presents an round massively parallel algorithm for approximation of maximum weighted -matchings, using near-linear memory per machine. Her…
Improved Local Computation Algorithm for Set Cover via Sparsification
Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld +1
We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most and each element is contained in at most sets, t…
Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples
Michael Kapralov, Slobodan Mitrović, Ashkan Norouzi-Fard +1
Given a source of iid samples of edges of an input graph with vertices and edges, how many samples does one need to compute a constant factor approximation to the maxim…
Adversarially Robust Submodular Maximization under Knapsack Constraints
Dmitrii Avdiukhin, Slobodan Mitrović, Grigory Yaroslavtsev +1
We propose the first adversarially robust algorithm for monotone submodular maximization under single and multiple knapsack constraints with scalable implementations in distributed…
Identifying Maximal Non-Redundant Integer Cone Generators
Slobodan Mitrović, Ruzica Piskac, Viktor Kunčak
A non-redundant integer cone generator (NICG) of dimension is a set of vectors from whose vector sum cannot be generated as a positive integer linear combinatio…
Weighted Matchings via Unweighted Augmentations
Buddhima Gamlath, Sagar Kale, Slobodan Mitrović +1
We design a generic method for reducing the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide eff…