40 citations · 242 across the 33 of their papers we have counts for
Showing 2015 · cs.DSShow all
3 papers · 2 filters
cs.DS2015★ 6 cited
Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions
Vitaly Feldman, Jan Vondrak
Submodular and fractionally subadditive (or equivalently XOS) functions play a fundamental role in combinatorial optimization, algorithmic game theory and machine learning. Motivat…
cs.DS2015
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles
Nicholas Harvey, Jan Vondrak
The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an…
cs.DS2015★ 1 cited
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
Alina Ene, Jan Vondrak, Yi Wu
We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate thes…