68 citations · 73 across the 5 of their papers we have counts for
6 papers
On the Hardness of Dominant Strategy Mechanism Design
Shahar Dobzinski, Shiri Ron, Jan Vondrák
We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered "easy": multi-unit auc…
On complex roots of the independence polynomial
Ferenc Bencs, Péter Csikvári, Piyush Srivastava +1
It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial of a graph of maximum degree at most does not vani…
Fixed-Price Approximations in Bilateral Trade
Zi Yang Kang, Francisco Pernice, Jan Vondrák
We consider the bilateral trade problem, in which two agents trade a single indivisible item. It is known that the only dominant-strategy truthful mechanism is the fixed-price mech…
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
Wenzheng Li, Jan Vondrák
We present a -approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximatio…
Short proofs for generalizations of the Lovász Local Lemma: Shearer's condition and cluster expansion
Nicholas J. A. Harvey, Jan Vondrák
The Lovász 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…
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
Chandra Chekuri, Jan Vondrák, Rico Zenklusen
We consider the problem of maximizing a non-negative submodular set function over a ground set subject to a variety of packing type constraints…