Quasi-Proportional Mechanisms: Prior-free Revenue Maximization (2009)
Mirrokni, Vahab, Muthukrishnan, S., Nadav, Uri
Inspired by Internet ad auction applications, we study the problem of allocating a single item via an auction when bidders place very different values on the item. We formulate this as the problem of...
Two-Stage Robust Network Design with Exponential Scenarios (2009)
Rohit Kh, Guy Kortsarz, Vahab Mirrokni, Mohammad R
Abstract. We study two-stage robust variants of combinatorial optimization problems like Steiner tree, Steiner forest, and uncapacitated facility location. The robust optimization problems,...
Robust PageRank and Locally Computable Spam Detection Features ∗ (2009)
Reid Andersen, John Hopcroft, Christian Borgs, Kamal Jain, Shanghua Teng, Jennifer Chayes, ...
Since the link structure of the web is an important element in ranking systems on search engines, web spammers widely use the link structure of the web to increase the rank of their pages. Various...
Approximating Submodular Functions Everywhere (2009)
Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Many interesting problems...
Online Stochastic Matching: Beating 1-1/e (2009)
Feldman, Jon, Mehta, Aranyak, Mirrokni, Vahab, Muthukrishnan, S.
We study the online stochastic bipartite matching problem, in a form motivated by display ad allocation on the Internet. In the online, but adversarial case, the celebrated result of Karp, Vazirani...
Non-monotone submodular maximization under matroid and knapsack constraints (2009)
Lee, Jon, Mirrokni, Vahab, Nagarjan, Viswanath, Sviridenko, Maxim
Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hypergraphs, certain...
On the complexity of Nash dynamics and Sink Equilibria (2009)
Mirrokni, Vahab, Skopalik, Alexander
Studying Nash dynamics is an important approach for analyzing the outcome of games with repeated selfish behavior of self-interested agents. Sink equilibria has been introduced by Goemans, Mirrokni,...
Bid Optimization in Broad-Match Ad auctions (2009)
Even-dar, Eyal, Mansour, Yishay, Mirrokni, Vahab, Muthukrishnan, S., Nadav, Uri
Ad auctions in sponsored search support ``broad match'' that allows an advertiser to target a large number of queries while bidding only on a limited number. While giving more expressiveness to...
Reid Andersen, Christian Borgs, Jennifer Chayes, Uriel Feige, Abraham Flaxman, Adam Kalai, ...
High-quality, personalized recommendations are a key feature in many online systems. Since these systems often have explicit knowledge of social network structures, the recommendations may...
Approximating Minimum-Power Network Design Problems (2008)
Guy Kortsarz, Vahab Mirrokni, Zeev Nutov, Elena Tsanko
Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of its nodes. Motivated by applications in...
The myth of the folk theorem (2008)
Christian Borgs, Adam Tauman Kalai, Jennifer Chayes, Vahab Mirrokni
A well-known result in game theory known as “the Folk Theorem ” suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the...
almost) optimal coordination mechanisms for unrelated maching scheduling (2008)
Yossi Azar, Kamal Jain, Vahab Mirrokni
We investigate the influence of different algorithmic choices on the approximation ratio in selfish scheduling. Our goal is to design local policies that minimize the inefficiency of resulting...
The myth of the folk theorem (2008)
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, Christos Papadimitriou
The folk theorem suggests that finding Nash Equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the problem of finding any (epsilon) Nash equilibrium for a...
The myth of the folk theorem (2008)
Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, Christos Papadimitriou
A well-known result in game theory known as “the Folk Theorem ” suggests that finding Nash equilibria in repeated games should be easier than in one-shot games. In contrast, we show that the...
Robust combinatorial optimization with exponential scenarios (2007)
Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab Mirrokni
Abstract. Following the well-studied two-stage optimization framework for stochastic optimization [15, 18], we study approximation algorithms for robust two-stage optimization problems with an...
Trust-based recommendation systems: An axiomatic approach (2007)
Reid Andersen, Christian Borgs, Jennifer Chayes, Uriel Feige, Abraham Flaxman, Adam Kalai, ...
High-quality, personalized recommendations are a key feature in many online systems. Since these systems often have explicit knowledge of social network structures, the recommendations may...
Tight information-theoretic lower bounds for combinatorial auctions (2007)
Vahab Mirrokni, Michael Schapira, Jan Vondrák
We provide tight information-theoretic lower bounds for the welfare maximization problem in combinatorial auctions. In this problem the goal is to partition m items between k bidders in a way that...
Robust combinatorial optimization with exponential scenarios (2007)
Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab Mirrokni
Following the well-studied two-stage optimization framework for stochastic optimization [14, 17], we study approximation algorithms for robust two-stage optimization problems with exponential number...
Robust combinatorial optimization with exponential scenarios (2007)
Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab Mirrokni
Following the well-studied two-stage optimization framework for stochastic optimization [14, 17], we study approximation algorithms for robust two-stage optimization problems with exponential number...
Tight information-theoretic lower bounds for welfare maximization in combinatorial auctions (2007)
Vahab Mirrokni, Michael Schapira, Jan Vondrák
We provide tight information-theoretic lower bounds for the welfare maximization problem in combinatorial auctions. In this problem the goal is to partition m items between k bidders in a way that...
Sink equilibria and convergence (2005)
Michel Goemans, Adrian Vetta, Vahab Mirrokni
We introduce the concept of a sink equilibrium. A sink equilibrium is a strongly connected component with no outgoing arcs in the strategy profile graph associated with a game. The strategy profile...
Cell Breathing in Wireless LANs: Algorithms and Evaluation (2004)
Paramvir Bahl, Mohammad T. Hajiaghayi, Kamal Jain, Vahab Mirrokni, Lili Qiu, Amin Saberi
Abstract — Wireless LAN administrators often have to deal with the problem of sporadic client congestion in popular locations within the network. Existing approaches that relieve congestion by...
When more than one processor is available to run a program, we can decrease the total computation time by running certain jobs in parallel. Given a set of jobs and their inter-dependencies, the...
Bell Labs Algorithms Pow Wow (1998)
Shepherd, F. B., Chekuri, Chandra, Gupta, Anuparn, Mirrokni, Vahab, Shachnai, Hadas
For two weeks researchers in algorithms gathered to remind each other of some old unsolved problems and to present some new ones. People broke off into groups according to their interest in certain...