Jan Vondrák

STOC Conference 2024 Conference Paper

A Constant-Factor Approximation for Nash Social Welfare with Subadditive Valuations

• Shahar Dobzinski
• Wenzheng Li
• Aviad Rubinstein
• Jan Vondrák

We present a constant-factor approximation algorithm for the Nash Social Welfare (NSW) maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a framework for NSW optimization which assumes two subroutines which (1) solve a configuration-type LP under certain additional conditions, and (2) round the fractional solution with respect to utilitarian social welfare. In particular, a constant-factor approximation for submodular valuations with value queries can also be derived from our framework.

STOC Conference 2024 Conference Paper

Prophet Inequalities with Cancellation Costs

• Farbod Ekbatani
• Rad Niazadeh
• Pranav Nuti
• Jan Vondrák

Most of the literature on online algorithms and sequential decision-making focuses on settings with “irrevocable decisions” where the algorithm’s decision upon arrival of the new input is set in stone and can never change in the future. One canonical example is the classic prophet inequality problem, where realizations of a sequence of independent random variables X 1 , X 2 ,… with known distributions are drawn one by one and a decision maker decides when to stop and accept the arriving random variable, with the goal of maximizing the expected value of their pick. We consider “prophet inequalities with recourse” in the linear buyback cost setting, where after accepting a variable X i , we can still discard X i later and accept another variable X j , at a buyback cost of f × X i . The goal is to maximize the expected net reward, which is the value of the final accepted variable minus the total buyback cost. Our first main result is an optimal prophet inequality in the regime of f ≥ 1, where we prove that we can achieve an expected reward 1+ f /1+2 f times the expected offline optimum. The problem is still open for 0< f <1 and we give some partial results in this regime. In particular, as our second main result, we characterize the asymptotic behavior of the competitive ratio for small f and provide almost matching upper and lower bounds that show a factor of 1−Θ( f log(1/ f )). Our results are obtained by two fundamentally different approaches: One is inspired by various proofs of the classical prophet inequality, while the second is based on combinatorial optimization techniques involving LP duality, flows, and cuts.

STOC Conference 2023 Conference Paper

Approximating Nash Social Welfare by Matching and Local Search

• Jugal Garg
• Edin Husic
• Wenzheng Li
• László A. Végh
• Jan Vondrák

For any >0, we give a simple, deterministic (4+)-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem, where the objective is to maximize the weighted geometric mean of agents’ valuations, and give an (ω + 2 + ) -approximation if the ratio between the largest weight and the average weight is at most ω. We also show that the 12-EFX envy-freeness property can be attained simultaneously with a constant-factor approximation. More precisely, we can find an allocation in polynomial time which is both 12-EFX and a (8+)-approximation to the symmetric NSW problem under submodular valuations. The previous best approximation factor under 12-EFX was linear in the number of agents.

SODA Conference 2023 Conference Paper

On complex roots of the independence polynomial

• Ferenc Bencs
• Péter Csikvári
• Piyush Srivastava 0001
• Jan Vondrák

The independence polynomial of a graph is the generating polynomial of all its independent sets. Formally, given a graph G, its independence polynomial Z G (λ) is given by Σ I λ | I |, where the sum is over all independent sets I of G. The independence polynomial has been an important object of study in both combinatorics and computer science. In particular, the algorithmic problem of estimating Z G (λ) for a fixed positive λ on an input graph G is a natural generalization of the problem of counting independent sets, and its study has led to some of the most striking connections between computational complexity and the theory of phase transitions. More surprisingly, the independence polynomial for negative and complex values of λ also turns out to be related to problems in statistical physics and combinatorics. In particular, the locations of the complex roots of the independence polynomial of bounded degree graphs turn out to be very closely related to the Lovász local lemma, and also to the questions in the computational complexity of counting. Consequently, the locations of such zeros have been studied in many works. In this direction, it is known from the work of Shearer [29] and of Scott and Sokal [27] - inspired by the study of the Lovász local lemma - that the independence polynomial Z G (λ) of a graph G of maximum degree at most d + 1 does not vanish provided that. Significant extensions of this result have recently been given in the case when λ is in the right half-plane (i. e. , when ℜλ ≥ 0) by Peters and Regts [26] and Bencs and Csikvári [9]. In this paper, our motivation is to further extend these results to find new zero free regions not only in the right half plane, but also in the left half-plane, that is, when ℜλ ≤ 0. We give new geometric criterions for establishing zero-free regions as well as for carrying out semi-rigorous numerical explorations. We then provide two examples of the (rigorous) use of these criterions, by establishing two new zero-free regions in the left-half plane. We also extend the results of Bencs and Csikvári [9] for the right half-plane using our framework. By a direct application of the interpolation method of Barvinok [5], combined with extensions due to Patel and Regts [25], our results also imply deterministic polynomial time approximation algorithms for the independence polynomial of bounded degree graphs in the new zero-free regions. * The arXiv version of the paper can be accessed at https: //arxiv. org/abs/2204. 04868.

SODA Conference 2023 Conference Paper

Secretary Problems: The Power of a Single Sample

• Pranav Nuti
• Jan Vondrák

In this paper, we investigate two variants of the secretary problem. In these variants, we are presented with a sequence of numbers X i that come from distributions D i, and that arrive in either random or adversarial order. We do not know what the distributions are, but we have access to a single sample Y i from each distribution D i. After observing each number, we have to make an irrevocable decision about whether we would like to accept it or not with the goal of maximizing the probability of selecting the largest number. The random order version of this problem was first studied by Correa et al. [SODA 2020] who managed to construct an algorithm that achieves a probability of 0. 4529. In this paper, we improve this probability to 0. 5009, almost matching an upper bound of ≃ 0. 5024 which we show follows from earlier work. We also show that there is an algorithm which achieves the probability of ≃ 0. 5024 asymptotically if no particular distribution is especially likely to yield the largest number. For the adversarial order version of the problem, we show that we can select the maximum number with a probability of 1/4, and that this is best possible. Our work demonstrates that unlike in the case of the expected value objective studied by Rubinstein et al. [ITCS 2020], knowledge of a single sample is not enough to recover the factor of success guaranteed by full knowledge of the distribution.

SODA Conference 2022 Conference Paper

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 mechanism: given commonly known distributions of the buyer's value B and the seller's value S, a price p is offered to both agents and trade occurs if S ≤ p ≤ B. The objective is to maximize either expected welfare or expected gains from trade. We improve the approximation ratios for several welfare maximization variants of this problem. When the agents' distributions are identical, we show that the optimal approximation ratio for welfare is. With just one prior sample from the common distribution, we show that a 3/4-approximation to welfare is achievable. When agents' distributions are not required to be identical, we show that a previously best-known (1–1/ e )-approximation can be strictly improved, but 1–1/ e is optimal if only the seller's distribution is known.

STOC Conference 2022 Conference Paper

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 auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfare-maximizing allocation with communication complexity that is poly-logarithmic in the input size. This immediately implies that welfare maximization can be achieved in ex-post equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multi-unit auctions with decreasing marginal values, we provide a dominant-strategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better than m 1−є that uses poly ( m , n ) bits of communication, where m is the number of items and n is the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves an O (√ m ) approximation with poly ( m , n ) communication is known. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones. En route, we answer an open question on the communication cost of implementing dominant strategy mechanisms for more than two players, and also solve some open problems in the area of simultaneous combinatorial auctions.

FOCS Conference 2021 Conference Paper

A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations

• Wenzheng Li
• Jan Vondrák

We present a 380-approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximation for Rado valuations [15].

SODA Conference 2021 Conference Paper

Estimating the Nash Social Welfare for coverage and other submodular valuations

• Wenzheng Li
• Jan Vondrák

We study the Nash Social Welfare problem: Given n agents with valuation functions v i: 2 [ m ] → ℝ +, partition [ m ] into S 1, …, S n so as to maximize. The problem has been shown to admit a constant-factor approximation for additive, budget-additive, and piecewise linear concave separable valuations; the case of submodular valuations is open. We provide a -approximation of the optimal value for several classes of submodular valuations: coverage, sums of matroid rank functions, and certain matching-based valuations.

STOC Conference 2020 Conference Paper

A polynomial lower bound on adaptive complexity of submodular maximization

• Wenzheng Li
• Paul Liu 0001
• Jan Vondrák

In large-data applications, it is desirable to design algorithms with a high degree of parallelization. In the context of submodular optimization, adaptive complexity has become a widely-used measure of an algorithm’s “sequentiality”. Algorithms in the adaptive model proceed in rounds, and can issue polynomially many queries to a function f in each round. The queries in each round must be independent, produced by a computation that depends only on query results obtained in previous rounds. In this work, we examine two fundamental variants of submodular maximization in the adaptive complexity model: cardinality-constrained monotone maximization, and unconstrained non-mono-tone maximization. Our main result is that an r -round algorithm for cardinality-constrained monotone maximization cannot achieve an approximation factor better than 1 − 1/ e − Ω(min{ 1/ r , log 2 n / r 3 }), for any r 0 is some constant). This is the first result showing that the number of rounds must blow up polynomially large as we approach the optimal factor of 1−1/ e . For the unconstrained non-monotone maximization problem, we show a positive result: For every instance, and every δ>0, either we obtain a (1/2−δ)-approximation in 1 round, or a (1/2+Ω(δ 2 ))-approximation in O (1/δ 2 ) rounds. In particular (and in contrast to the cardinality-constrained case), there cannot be an instance where (i) it is impossible to achieve an approximation factor better than 1/2 regardless of the number of rounds, and (ii) it takes r rounds to achieve a factor of 1/2− O (1/ r ).

TCS Journal 2020 Journal Article

Tight bounds on ℓ1 approximation and learning of self-bounding functions

• Vitaly Feldman
• Pravesh Kothari
• Jan Vondrák

We study the complexity of learning and approximation of self-bounding functions over the uniform distribution on the Boolean hypercube { 0, 1 } n. Informally, a function f: { 0, 1 } n → R is self-bounding if for every x ∈ { 0, 1 } n, f ( x ) upper bounds the sum of all the n marginal decreases in the value of the function at x. Self-bounding functions include such well-known classes of functions as submodular and fractionally-subadditive (XOS) functions. They were introduced by Boucheron et al. (2010) in the context of concentration of measure inequalities. Our main result is a nearly tight ℓ 1 -approximation of self-bounding functions by low-degree juntas. Specifically, all self-bounding functions can be ϵ-approximated in ℓ 1 by a polynomial of degree O ˜ ( 1 / ϵ ) over 2 O ˜ ( 1 / ϵ ) variables. We show that both the degree and junta-size are optimal up to logarithmic terms. Previous techniques considered stronger ℓ 2 approximation and proved nearly tight bounds of Θ ( 1 / ϵ 2 ) on the degree and 2 Θ ( 1 / ϵ 2 ) on the number of variables. Our bounds rely on the analysis of noise stability of self-bounding functions together with a stronger connection between noise stability and ℓ 1 approximation by low-degree polynomials. This technique can also be used to get tighter bounds on ℓ 1 approximation by low-degree polynomials and a faster learning algorithm for halfspaces. These results lead to improved and in several cases almost tight bounds for PAC and agnostic learning of self-bounding functions relative to the uniform distribution. In particular, assuming hardness of learning juntas, we show that PAC and agnostic learning of self-bounding functions have complexity of n Θ ˜ ( 1 / ϵ ).

SODA Conference 2018 Conference Paper

Computing the Independence Polynomial: from the Tree Threshold down to the Roots

• Nicholas J. A. Harvey
• Piyush Srivastava 0001
• Jan Vondrák

FOCS Conference 2015 Conference Paper

An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles

• Nicholas J. A. Harvey
• Jan Vondrák

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 outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient algorithm for a general setting primarily characterized by a product structure on the probability space. In this work we present an efficient algorithm for a much more general setting. Our main assumption is that there exist certain functions, called resampling oracles, that can be invoked to address the undesired occurrence of the events. We show that, in all scenarios to which the original Lovasz Local Lemma applies, there exist resampling oracles, although they are not necessarily efficient. Nevertheless, for essentially all known applications of the Lovasz Local Lemma and its generalizations, we have designed efficient resampling oracles. As applications of these techniques, we present new results for packings of Latin transversals, rainbow matchings and rainbow spanning trees.

SODA Conference 2015 Conference Paper

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 case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature c. In the case of submodular maximization with curvature c, we obtain a (1 — c / e )-approximation — the first improvement over the greedy (1 — e − c )/ c -approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

SODA Conference 2015 Conference Paper

Sperner's Colorings, Hypergraph Labeling Problems and Fair Division

• Maryam Mirzakhani
• Jan Vondrák

FOCS Conference 2015 Conference Paper

Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions

• Vitaly Feldman
• Jan Vondrák

Submodular and fractionally subadditive (or equivalently XOS) functions play a fundamental role in combinatorial optimization, algorithmic game theory and machine learning. Motivated by learnability of these classes of functions from random examples, we consider the question of how well such functions can be approximated by low-degree polynomials in ℓ 2 norm over the uniform distribution. This question is equivalent to understanding the concentration of Fourier weight on low-degree coefficients, a central concept in Fourier analysis. Denoting the smallest degree sufficient to approximate f in ℓ 2 norm within ∈ by deg ∈ (ℓ 2 )(f), we show that: For any submodular function f: {0, 1} n → [0, 1], deg ∈ (ℓ 2 )(f) = O(log(1/∈)/∈ 4/5 ) and there is a submodular function that requires degree Ω(1/∈ 4/5 ). : For any XOS function f: {0, 1} → [0, 1], deg ∈ (ℓ 2 ) (f) = O(1/∈) and there exists an XOS function that requires degree Ω(1/∈). This improves on previous approaches that all showed an upper bound of O(1/∈ 2 ) for submodular [CKKL12], [FKV13], [FV13] and XOS [FV13] functions. The best previous lower bound was Ω(1/∈ 2/3 ) for monotone submodular functions [FKV13]. Our techniques reveal new structural properties of submodular and XOS functions and the upper bounds lead to nearly optimal PAC learning algorithms for these classes of functions.

SODA Conference 2014 Conference Paper

Fast algorithms for maximizing submodular functions

• Ashwinkumar Badanidiyuru
• Jan Vondrák

There has been much progress recently on improved approximations for problems involving submodular objective functions, and many interesting techniques have been developed. However, the resulting algorithms are often slow and impractical. In this paper we develop algorithms that match the best known approximation guarantees, but with significantly improved running times, for maximizing a monotone submodular function f: 2 [ n ] → ℝ + subject to various constraints. As in previous work, we measure the number of oracle calls to the objective function which is the dominating term in the running time. Our first result is a simple algorithm that gives a (1 − 1/∊ − ∊)-approximation for a cardinality constraint using queries, and a 1/( p + 2 ℓ + 1 + ∊)-approximation for the intersection of a p -system and ℓ knapsack (linear) constraints using queries. This is the first approximation for a p -system combined with linear constraints. (We also show that the factor of p cannot be improved for maximizing over a p -system.) The main idea behind these algorithms serves as a building block in our more sophisticated algorithms. Our main result is a new variant of the continuous greedy algorithm, which interpolates between the classical greedy algorithm and a truly continuous algorithm. We show how this algorithm can be implemented for matroid and knapsack constraints using Õ ( n 2 ) oracle calls to the objective function. (Previous variants and alternative techniques were known to use at least Õ ( n 4 ) oracle calls.) This leads to an -time (1 − 1/∊ − ∊)-approximation for a matroid constraint. For a knapsack constraint, we develop a more involved (1 − 1/∊ − ∊)-approximation algorithm that runs in time.

STOC Conference 2014 Conference Paper

Multiway cut, pairwise realizable distributions, and descending thresholds

• Ankit Sharma 0001
• Jan Vondrák

SODA Conference 2013 Conference Paper

Communication Complexity of Combinatorial Auctions with Submodular Valuations

• Shahar Dobzinski
• Jan Vondrák

We prove the first communication complexity lower bound for constant-factor approximation of the submodular welfare problem. More precisely, we show that a -approximation (≃ 0. 816) for welfare maximization in combinatorial auctions with submodular valuations would require exponential communication. We also show NP-hardness of -approximation in a computational model where each valuation is given explicitly by a table of constant size. Both results rule out better than (1 − )-approximations in every oracle model with a separate oracle for each player, such as the demand oracle model. Our main tool is a new construction of monotone submodular functions that we call multi-peak submodular functions. Roughly speaking, given a family of sets, we construct a monotone submodular function f with a high value f ( S ) for every set S ∊ (a “peak”), and a low value on every set that does not intersect significantly any set in. We also study two other related problems: max-min allocation (for which we also get hardness of -approximation, in both models), and combinatorial public projects (for which we prove hardness of -approximation in the communication model, and hardness of -approximation in the computational model, using constant size valuations).

SODA Conference 2013 Conference Paper

Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems

• Alina Ene
• Jan Vondrák
• Yi Wu 0002

We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations that we call respectively the Local Distribution LP, and the Lovász relaxation. The Local Distribution LP is generally stronger than the Lovász relaxation, but applicable only to Min-CSP with predicates of constant size. The relaxations coincide in some cases such as Multiway Cut where they are both equivalent to the CKR relaxation. We show that the Lovász relaxation gives a (2 − 2/ k )-approximation for Submodular Multiway Partition with k terminals, improving a recent 2-approximation [2]. We prove that this factor is optimal in two senses: (1) A (2 − 2/ k − ∊)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries (in the oracle model), or imply NP = RP (for certain explicit submodular functions). (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2 − 2/ k − ∊)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems [19, 6], also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Local Distribution LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Local Distribution LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence.

SODA Conference 2013 Conference Paper

Online Submodular Welfare Maximization: Greedy is Optimal

• Michael Kapralov
• Ian Post
• Jan Vondrák

We prove that no online algorithm (even randomized, against an oblivious adversary) is better than 1/2-competitive for welfare maximization with coverage valuations, unless NP = RP. Since the Greedy algorithm is known to be 1/2-competitive for monotone submodular valuations, of which coverage is a special case, this proves that Greedy provides the optimal competitive ratio. On the other hand, we prove that Greedy in a stochastic setting with i. i. d. items and valuations satisfying diminishing returns is (1 − 1/ e )-competitive, which is optimal even for coverage valuations, unless NP = RP. For online budget-additive allocation, we prove that no algorithm can be 0. 612-competitive with respect to a natural LP which has been used previously for this problem.

FOCS Conference 2013 Conference Paper

Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas

• Vitaly Feldman
• Jan Vondrák

We investigate the approximability of several classes of real-valued functions by functions of a small number of variables (juntas). Our main results are tight bounds on the number of variables required to approximate a function f: {0, 1} n → [0, 1] within ℓ 2 -error ϵ over the uniform distribution: If f is sub modular, then it is ϵ-close to a function of O(1/ϵ 2 log 1/ϵ) variables. This is an exponential improvement over previously known results FeldmanKV: 13. We note that Ω(1/ϵ 2 ) variables are necessary even for linear functions. If f is fractionally sub additive (XOS) it is ε-close to a function of 2 O(1/ϵ2) variables. This result holds for all functions with low total ℓ 1 -influence and is a real-valued analogue of Fried gut's theorem for boolean functions. We show that 2 Ω(1/ϵ) variables are necessary even for XOS functions. As applications of these results, we provide learning algorithms over the uniform distribution. For XOS functions, we give a PAC learning algorithm that runs in time 2 1/poly(ϵ) poly(n). For sub modular functions we give an algorithm in the more demanding PMAC learning model BalcanHarvey: [12] which requires a multiplicative (1 + γ) factor approximation with probability at least 1 - ϵ over the target distribution. Our uniform distribution algorithm runs in time 2 1/poly(γϵ) poly(n). This is the first algorithm in the PMAC model that can achieve a constant approximation factor arbitrarily close to 1 for all sub modular functions (even over the uniform distribution). It relies crucially on our approximation by junta result. As follows from the lower bounds in FeldmanKV: 13 both of these algorithms are close to optimal. We also give applications for proper learning, testing and agnostic learning with value queries of these classes.

STOC Conference 2012 Conference Paper

From query complexity to computational complexity

• Shahar Dobzinski
• Jan Vondrák

We consider submodular optimization problems, and provide a general way of translating oracle inapproximability results arising from the symmetry gap technique to computational complexity inapproximability results, where the submodular function is given explicitly (under the assumption that NP ≠ RP). Applications of our technique include an optimal computational hardness of (1/2 + ε)-approximation for maximizing a symmetric nonnegative submodular function, an optimal hardness of (1-(1-1/k) k + ε)-approximation for welfare maximization in combinatorial auctions with k submodular bidders (for constant k), super-constant hardness for maximizing a nonnegative submodular function over matroid bases, and tighter bounds for maximizing a monotone submodular function subject to a cardinality constraint. Unlike the vast majority of computational inapproximability results, our approach does not use the PCP machinery or the Unique Games Conjecture, but relies instead on a direct reduction from Unique-SAT using list-decodable codes.

FOCS Conference 2011 Conference Paper

Limitations of Randomized Mechanisms for Combinatorial Auctions

• Shaddin Dughmi
• Jan Vondrák

The design of computationally efficient and incentive compatible mechanisms that solve or approximate fundamental resource allocation problems is the main goal of algorithmic mechanism design. A central example in both theory and practice is welfare-maximization in combinatorial auctions. Recently, a randomized mechanism has been discovered for combinatorial auctions that is truthful in expectation and guarantees a (1-1/e)-approximation to the optimal social welfare when players have coverage valuations [DRY11]. This approximation ratio is the best possible even for non-truthful algorithms, assuming P does not equal NP. Given the recent sequence of negative results for combinatorial auctions under more restrictive notions of incentive compatibility, this development raises a natural question: Are truthful-in-expectation mechanisms compatible with polynomial-time approximation in a way that deterministic or universally truthful mechanisms are not? In particular, can polynomial-time truthful-in-expectation mechanisms guarantee a near-optimal approximation ratio for more general variants of combinatorial auctions? We prove that this is not the case. Specifically, the result of [DRY11] cannot be extended to combinatorial auctions with sub modular valuations in the value oracle model. (Absent strategic considerations, a (1-1/e)-approximation is still achievable in this setting.) More precisely, we prove that there is a constant \gamma>0 such that there is no randomized mechanism that is truthful-in-expectation -- or even approximately truthful-in-expectation -- and guarantees an m^{-\gamma}-approximation to the optimal social welfare for combinatorial auctions with sub modular valuations in the value oracle model. We also prove an analogous result for the flexible combinatorial public projects (CPP) problem, where a truthful-in-expectation $(1-1/e)$-approximation for coverage valuations has been recently developed [Dughmi11]. We show that there is no truthful-in-expectation -- or even approximately truthful-in-expectation -- mechanism that achieves an m^{-\gamma}-approximation to the optimal social welfare for combinatorial public projects with sub modular valuations in the value oracle model. Both our results present an unexpected separation between coverage functions and sub modular functions, which does not occur for these problems without strategic considerations.

SODA Conference 2011 Conference Paper

Multi-budgeted Matchings and Matroid Intersection via Dependent Rounding

• Chandra Chekuri
• Jan Vondrák
• Rico Zenklusen

Motivated by multi-budgeted optimization and other applications, we consider the problem of randomly rounding a fractional solution x in the (non-bipartite graph) matching and matroid intersection polytopes. We show that for any fixed δ > 0, a given point x can be rounded to a random solution R such that E [1 R ] = (1 − δ)x and any linear function of x satisfies dimension-free Chernoff-Hoeffding concentration bounds (the bounds depend on S and the expectation μ). We build on and adapt the swap rounding scheme in our recent work [9] to achieve this result. Our main contribution is a non-trivial martingale based analysis framework to prove the desired concentration bounds. In this paper we describe two applications. We give a randomized PTAS for matroid intersection and matchings with any fixed number of budget constraints. We also give a deterministic PTAS for the case of matchings. The concentration bounds also yield related results when the number of budget constraints is not fixed. As a second application we obtain an algorithm to compute in polynomial time an ε-approximate Pareto-optimal set for the multi-objective variants of these problems, when the number of objectives is a fixed constant. We rely on a result of Papadimitriou and Yannakakis [26].

STOC Conference 2011 Conference Paper

Submodular function maximization via the multilinear relaxation and contention resolution schemes

• Jan Vondrák
• Chandra Chekuri
• Rico Zenklusen

SODA Conference 2011 Conference Paper

Submodular Maximization by Simulated Annealing

• Shayan Oveis Gharan
• Jan Vondrák

We consider the problem of maximizing a non-negative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [9] showed a 2/5-approximation for the unconstrained problem and also proved that no approximation better than 1/2 is possible in the value oracle model. Constant-factor approximation has been also known for submodular maximization subject to a matroid independence constraint (a factor of 0. 309 [33]) and for submodular maximization subject to a matroid base constraint, provided that the fractional base packing number v is bounded away from 1 (a 1/4-approximation assuming that v ≥ 2 [33]). In this paper, we propose a new algorithm for submodular maximization which is based on the idea of simulated annealing. We prove that this algorithm achieves improved approximation for two problems: a 0. 41-approximation for unconstrained submodular maximization, and a 0. 325-approximation for submodular maximization subject to a matroid independence constraint. On the hardness side, we show that in the value oracle model it is impossible to achieve a 0. 478-approximation for submodular maximization subject to a matroid independence constraint, or a 0. 394-approximation subject to a matroid base constraint in matroids with two disjoint bases. Even for the special case of cardinality constraint, we prove it is impossible to achieve a 0. 491-approximation. (Previously it was conceivable that a 1/2-approximation exists for these problems.) It is still an open question whether a 1/2-approximation is possible for unconstrained submodular maximization.

FOCS Conference 2010 Conference Paper

Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures

• Chandra Chekuri
• Jan Vondrák
• Rico Zenklusen

We consider the problem of randomly rounding a fractional solution x in an integer polytope P ⊆ [0, 1] n to a vertex X of P, so that E[X] = x. Our goal is to achieve concentration properties for linear and submodular functions of the rounded solution. Such dependent rounding techniques, with concentration bounds for linear functions, have been developed in the past for two poly topes: the assignment poly tope (that is, bipartite matchings and 6-matchings) [32], [19], [23], and more recently for the spanning tree poly tope [2]. These schemes have led to a number of new algorithmic results. In this paper we describe a new swap rounding technique which can be applied in a variety of settings including matroids and matroid intersection, while providing Chernoff-type concentration bounds for linear and submodular functions of the rounded solution. In addition to existing techniques based on negative correlation, we use a martingale argument to obtain an exponential tail estimate for monotone submodular functions. The rounding scheme explicitly exploits exchange properties of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds. Matroids and matroid intersection provide a unifying framework for several known applications [19], [23], [7], [22], [2] as well as new ones, and their generality allows a richer set of constraints to be incorporated easily. We give some illustrative examples, with a more comprehensive discussion deferred to a later version of the paper.

STOC Conference 2010 Conference Paper

Matroid matching: the power of local search

• Jon Lee 0001
• Maxim Sviridenko
• Jan Vondrák

We consider the classical matroid matching problem. Unweighted matroid matching for linear matroids was solved by Lovasz, and the problem is known to be intractable for general matroids. We present a PTAS for unweighted matroid matching for general matroids. In contrast, we show that natural LP relaxations have an Ω(n) integrality gap and moreover, Ω(n) rounds of the Sherali-Adams hierarchy are necessary to bring the gap down to a constant. More generally, for any fixed k>=2 and ε>0, we obtain a (k/2+ε)-approximation for matroid matching in k-uniform hypergraphs, also known as the matroid k-parity problem. As a consequence, we obtain a (k/2+ε)-approximation for the problem of finding the maximum-cardinality set in the intersection of k matroids. We have also designed a 3/2-approximation for the weighted version of a special case of matroid matching, the matchoid problem.

FOCS Conference 2009 Conference Paper

Symmetry and Approximability of Submodular Maximization Problems

• Jan Vondrák

A number of recent results on optimization problems involving submodular functions have made use of the "multilinear relaxation" of the problem. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of "symmetry gap". Our main result is that for any fixed instance that exhibits a certain "symmetry gap" in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, e. g. the optimality of (1-1/e)-approximation for monotone submodular maximization under a cardinality constraint, and the impossibility of (1/2+epsilon)-approximation for unconstrained (non-monotone) submodular maximization. It follows from our result that (1/2+epsilon)-approximation is also impossible for non-monotone submodular maximization subject to a (non-trivial) matroid constraint. On the algorithmic side, we present a 0. 309-approximation for this problem, improving the previously known factor of 1/4-o(1). As another application, we consider the problem of maximizing a non-monotone submodular function over the bases of a matroid. A (1/6-o(1))-approximation has been developed for this problem, assuming that the matroid contains two disjoint bases. We show that the best approximation one can achieve is indeed related to packings of bases in the matroid. Specifically, for any k≫=2, there is a class of matroids of fractional base packing number nu = k/(k-1), such that any algorithm achieving a better than (1-1/nu)-approximation for this class would require exponentially many value queries. On the positive side, we present a 1/2 (1-1/nu-o(1))-approximation algorithm for the same problem. Our hardness results hold in fact for very special symmetric instances. For such symmetric instances, we show that the approximation factors of 1/2 (for submodular maximization subject to a matroid constraint) and 1-1/nu (for a matroid base constraint) can be achieved algorithmically and hence are optimal.

STOC Conference 2008 Conference Paper

Optimal approximation for the submodular welfare problem in the value oracle model

• Jan Vondrák

In the Submodular Welfare Problem, m items are to be distributed among n players with utility functions w i : 2 [m] → R + . The utility functions are assumed to be monotone and submodular. Assuming that player i receives a set of items S i , we wish to maximize the total utility ∑ i=1 n w i (S i ). In this paper, we work in the value oracle model where the only access to the utility functions is through a black box returning w i (S) for a given set S. Submodular Welfare is in fact a special case of the more general problem of submodular maximization subject to a matroid constraint : max{f(S): S ∈ I}, where f is monotone submodular and I is the collection of independent sets in some matroid. For both problems, a greedy algorithm is known to yield a 1/2-approximation [21, 16]. In special cases where the matroid is uniform (I = S: |S| ≤ k) [20] or the submodular function is of a special type [4, 2], a (1-1/e)-approximation has been achieved and this is optimal for these problems in the value oracle model [22, 6, 15]. A (1-1/e)-approximation for the general Submodular Welfare Problem has been known only in a stronger demand oracle model [4], where in fact 1-1/e can be improved [9]. In this paper, we develop a randomized continuous greedy algorithm which achieves a (1-1/e)-approximation for the Submodular Welfare Problem in the value oracle model. We also show that the special case of n equal players is approximation resistant, in the sense that the optimal (1-1/e)-approximation is achieved by a uniformly random solution. Using the pipage rounding technique [1, 2], we obtain a (1-1/e)-approximation for submodular maximization subject to any matroid constraint. The continuous greedy algorithm has a potential of wider applicability, which we demonstrate on the examples of the Generalized Assignment Problem and the AdWords Assignment Problem.

FOCS Conference 2007 Conference Paper

Maximizing Non-Monotone Submodular Functions

• Uriel Feige
• Vahab Mirrokni
• Jan Vondrák

Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.

FOCS Conference 2006 Conference Paper

Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e

• Uriel Feige
• Jan Vondrák

Combinatorial allocation problems require allocating items to players in a way that maximizes the total utility. Two such problems received attention recently, and were addressed using the same linear programming (LP) relaxation. In the maximum submodular welfare (SMW) problem, utility functions of players are submodular, and for this case Dobzinski and Schapira [SODA 2006] showed an approximation ratio of 1 - 1/e. In the generalized assignment problem (GAP) utility functions are linear but players also have capacity constraints. GAP admits a (1 - 1/e)-approximation as well, as shown by Fleischer, Goemans, Mirrokni and Sviridenko [SODA 2006]. In both cases, the approximation ratio was in fact shown for a more general version of the problem, for which improving 1 - 1/e is NP-hard. In this paper, we show how to improve the 1 - 1/e approximation ratio, both for SMW and for GAP. A common theme in both improvements is the use of a new and optimal fair contention resolution technique. However, each of the improvements involves a different rounding procedure for the above mentioned LP. In addition, we prove APX-hardness results for SMW (such results were known for GAP). An important feature of our hardness results is that they apply even in very restricted settings, e. g. when every player has nonzero utility only for a constant number of items

SODA Conference 2005 Conference Paper

Adaptivity and approximation for stochastic packing problems

• Brian C. Dean
• Michel X. Goemans
• Jan Vondrák

FOCS Conference 2004 Conference Paper

Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity

• Brian C. Dean
• Michel X. Goemans
• Jan Vondrák

We consider a stochastic variant of the NP-hard 0/1 knapsack problem in which item values are deterministic and item sizes are independent random variables with known, arbitrary distributions. Items are placed in the knapsack sequentially, and the act of placing an item in the knapsack instantiates its size. Our goal is to compute a solution "policy" that maximizes the expected value of items placed in the knapsack, and we consider both non-adaptive policies (that designate a priori a fixed sequence of items to insert) and adaptive policies (that can make dynamic choices based on the instantiated sizes of items placed in the knapsack thus far). We show that adaptivity provides only a constant-factor improvement by demonstrating a greedy non-adaptive algorithm that approximates the optimal adaptive policy within a factor of 7. We also design an adaptive polynomial-time algorithm which approximates the optimal adaptive policy within a factor of 5 + /spl epsiv/, for any constant /spl epsiv/ > 0.

SODA Conference 2004 Conference Paper

Covering minimum spanning trees of random subgraphs

• Michel X. Goemans
• Jan Vondrák