42 citations · 96 across the 11 of their papers we have counts for
14 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…
Deterministic -Approximate Maximum Matching with Passes in the Semi-Streaming Model and Beyond
Manuela Fischer, Slobodan Mitrović, Jara Uitto
We present a deterministic -approximate maximum matching algorithm in passes in the semi-streaming model, solving the long-standing o…
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…
Beyond -Approximation for Submodular Maximization on Massive Data Streams
Ashkan Norouzi-Fard, Jakub Tarnawski, Slobodan Mitrović +3
Many tasks in machine learning and data mining, such as data diversification, non-parametric learning, kernel machines, clustering etc., require extracting a small but representati…
Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
Mohsen Ghaffari, Themis Gouleakis, Christian Konrad +2
We present -round algorithms in the Massively Parallel Computation (MPC) model, with memory per machine, that compute a maximal independent set, a $1+…
A Fast Algorithm for Separated Sparsity via Perturbed Lagrangians
Aleksander Mądry, Slobodan Mitrović, Ludwig Schmidt
Sparsity-based methods are widely used in machine learning, statistics, and signal processing. There is now a rich class of structured sparsity approaches that expand the modeling…
Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach
Slobodan Mitrović, Ilija Bogunovic, Ashkan Norouzi-Fard +2
We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fa…
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry +3
For over a decade now we have been witnessing the success of {\em massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for…
Robust Submodular Maximization: A Non-Uniform Partitioning Approach
Ilija Bogunovic, Slobodan Mitrović, Jonathan Scarlett +1
We study the problem of maximizing a monotone submodular function subject to a cardinality constraint , with the added twist that a number of items from the returned set may…
Homometric sets in trees
Radoslav Fulek, Slobodan Mitrović
Let denote a simple graph with the vertex set and the edge set . The profile of a vertex set denotes the multiset of pairwise distances between t…