42 citations · 96 across the 11 of their papers we have counts for
4 papers · 1 filter
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…