40 citations · 242 across the 33 of their papers we have counts for
Showing 2013 · cs.DSShow all
3 papers · 2 filters
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★ 3 cited
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…
cs.DS2013★ 25 cited
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…