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