Publications by Slobodan Mitrovic

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Mikhail Kapralov, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

Weighted Matchings via Unweighted Augmentations

Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...

ASSOC COMPUTING MACHINERY2019

Round Compression for Parallel Matching Algorithms

Slobodan Mitrovic, Aleksander Madry

For over a decade now we have been witnessing the success of massive parallel computation (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for their success is the fact that these frameworks are able to accurately capture th ...

ASSOC COMPUTING MACHINERY2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Slobodan Mitrovic, Mohsen Ghaffari

We present O(log log n)-round algorithms in the Massively Parallel Computation (MPC) model, with a(n) memory per machine, that compute a maximal independent set, a 1 + epsilon approximation of maximum matching, and a 2 + epsilon approximation of minimum ve ...

ASSOC COMPUTING MACHINERY2018

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Volkan Cevher, Ilija Bogunovic, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakub Tarnawski

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 fashion and (ii) m items from the algorithm’s memory might be removed after th ...

2017

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

We study the problem of maximizing a monotone submodular function subject to a cardinality constraint

k

, with the added twist that a number of items

\tau

from the returned set may be removed. We focus on the worst-case setting considered in Orlin et al ...

2017

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic, Slobodan Mitrovic

Abstract—In this paper, we consider the problem of maximizing a monotone submodular function subject to a cardinality constraint, with two added twists: The computation is distributed across a number of machines, and we require the solution to be robust ag ...

2017

Coupled tomography and distinct-element-method approach to exploring the granular media microstructure in a jamming hourglass

Giorgio Margaritondo, Michaël Unser, Thomas Liebling, Daniel Sage, Lionel Pournin, Slobodan Mitrovic, Marco Ramaioli, Michel Tsukahara, Vincent Gajdosik

We describe an approach for exploring microscopic properties of granular media that couples x-ray microtomography and distinct-element-method (DEM) simulations through image analysis. We illustrate it via the study of the intriguing phenomenon of instant a ...

APS2008

Three-dimensional dispersion induced by extreme tensile strain in La_(2−x)Sr_xCuO_4 films

Davor Pavuna, Slobodan Mitrovic, Dominique Cloëtta, Claudia Cancellieri, Mike Abrecht

The electronic band structure probed by angle-resolved photoemission spectroscopy on thin epitaxial La_(2−x)Sr_(x)CuO_(4) films under extreme tensile strain shows anomalous features compatible with c-axis dispersion. This result is in striking contrast wit ...

2006

Angle-resolved photoemission spectroscopic properties of quasi-one-dimensional crystals

Slobodan Mitrovic

Abstract Electronic properties of low-dimensional systems — and particularly quasi-one-dimensional systems — together with related correlated electron phenomena have for quite some time been at the very frontier of condensed matter physics. The interest ra ...

EPFL2004

Slobodan Mitrovic

Graph Chatbot

Chat with Graph Search

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Weighted Matchings via Unweighted Augmentations

Round Compression for Parallel Matching Algorithms

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Coupled tomography and distinct-element-method approach to exploring the granular media microstructure in a jamming hourglass

Three-dimensional dispersion induced by extreme tensile strain in La_(2−x)Sr_xCuO_4 films

Angle-resolved photoemission spectroscopic properties of quasi-one-dimensional crystals

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Three-dimensional dispersion induced by extreme tensile strain in La_(2−x)Sr_xCuO_4 films

Angle-resolved photoemission spectroscopic properties of quasi-one-dimensional crystals

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Weighted Matchings via Unweighted Augmentations

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Robust Submodular Maximization: A Non-Uniform Partitioning Approach

Coupled tomography and distinct-element-method approach to exploring the granular media microstructure in a jamming hourglass

A Distributed Algorithm for Partitioned Robust Submodular Maximization

Round Compression for Parallel Matching Algorithms