Zobrazeno 1 - 10
of 239
pro vyhledávání: '"Vondrak, Jan"'
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
Externí odkaz:
http://arxiv.org/abs/2404.00527
We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentive-compatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a wid
Externí odkaz:
http://arxiv.org/abs/2402.14173
We present a constant-factor approximation algorithm for the Nash social welfare maximization problem with subadditive valuations accessible via demand queries. More generally, we propose a template for NSW optimization by solving a configuration-typ
Externí odkaz:
http://arxiv.org/abs/2309.04656
Autor:
Park, Bryan, Vondrák, Jan
We revisit the Kahn-Kalai conjecture, recently proved in striking fashion by Park and Pham, and present a slightly reformulated simple proof which has a few advantages: (1) it works for non-uniform product measures, (2) it gives near-optimal bounds e
Externí odkaz:
http://arxiv.org/abs/2306.12576
The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been in
Externí odkaz:
http://arxiv.org/abs/2305.00122
For any $\eps>0$, we give a simple, deterministic $(4+\eps)$-approximation algorithm for the Nash social welfare (NSW) problem under submodular valuations. We also consider the asymmetric variant of the problem, where the objective is to maximize the
Externí odkaz:
http://arxiv.org/abs/2211.03883
Autor:
Nuti, Pranav, Vondrák, Jan
In this paper, we study contention resolution schemes for matchings. Given a fractional matching $x$ and a random set $R(x)$ where each edge $e$ appears independently with probability $x_e$, we want to select a matching $M \subseteq R(x)$ such that $
Externí odkaz:
http://arxiv.org/abs/2211.03599
Autor:
Nuti, Pranav, Vondrák, Jan
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 $\mathcal{D}_i$, and that arrive in either random or adversarial order. We do not k
Externí odkaz:
http://arxiv.org/abs/2208.09159
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
Externí odkaz:
http://arxiv.org/abs/2206.00334
It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial $Z_G(\lambda)$ of a graph $G$ of maximum degree at most $d+1$ does not vanish provided that $\vert{\lambda}\vert \leq \frac{d^d}{(d+1)^{d+1
Externí odkaz:
http://arxiv.org/abs/2204.04868