40 citations · 242 across the 33 of their papers we have counts for
4 papers · 1 filter
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…
Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds
Ankit Sharma, Jan Vondrák
We design new approximation algorithms for the Multiway Cut problem, improving the previously known factor of 1.32388 [Buchbinder et al., 2013]. We proceed in three steps. First, w…
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
Vitaly Feldman, Jan Vondrak
We investigate the approximability of several classes of real-valued functions by functions of a small number of variables ({\em juntas}). Our main results are tight bounds on the…
Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees
Vitaly Feldman, Pravesh Kothari, Jan Vondrak
We study the complexity of approximate representation and learning of submodular functions over the uniform distribution on the Boolean hypercube . Our main result is th…