63 citations · 181 across the 15 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.DS2013
Optimal approximation for submodular and supermodular optimization with bounded curvature
Maxim Sviridenko, Jan Vondrák, Justin Ward
We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the ca…
cs.DS2013
Submodular Stochastic Probing on Matroids
Marek Adamczyk, Maxim Sviridenko, Justin Ward
In a stochastic probing problem we are given a universe , where each element is active independently with probability , and only a probe of e can tell us whether…
cs.DS2013★ 9 cited
Large Neighborhood Local Search for the Maximum Set Packing Problem
Maxim Sviridenko, Justin Ward
In this paper we consider the classical maximum set packing problem where set cardinality is upper bounded by . We show how to design a variant of a polynomial-time local search…