NovoEd, San Francisco, CA, USA
Christian Borgs, Jennifer T. Chayes, Nicole Immorlica, Mohammad Mahdian, Amin Saberi
Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005 – EC
We study a multi-unit auction with multiple bidders, each of whom has a private valuation and a budget. The truthful mechanisms of such an auction are characterized, in the sense that, under standard assumptions, we prove that it is impossible to ...
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani
46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005 – FOCS
How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a tradeoff revealing LP and use it ...
Kamal Jain, Mohammad Mahdian, Amin Saberi
We present a simple and natural greedy algorithm for the metric uncapacitated facility location problem achieving an approximation guarantee of 1.61. We use this algorithm to find better approximation algorithms for the capacitated facility location ...
Christos Gkantsidis, Milena Mihail, Amin Saberi
We quantify the effectiveness of random walks for searching and construction of unstructured peer-to-peer (P2P) networks. For searching, we argue that random walks achieve improvement over flooding in the case of clustered overlay topologies and in ...
Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay V. Vazirani
Journal of the ACM, vol. 50,no. 6,2003 – JACM
In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation ...
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani
Journal of the ACM, vol. 54,no. 5,2007 – JACM
How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP ...
Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani
43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002 – FOCS
Although the study of market equilibria has occupied center stage within Mathematical Economics for over a century, polynomial time algorithms for such questions have so far evaded researchers. We provide the first such algorithm for the linear ...
Christos Gkantsidis, Milena Mihail, Amin Saberi
ACM SIGMETRICS Performance Evaluation Review, vol. 31,no. 1,2003 – PER
It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to ...
Christian Borgs, Jennifer T. Chayes, Mohammad Mahdian, Amin Saberi
Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004 – KDD
We propose to use the community structure of Usenet for organizing and retrieving the information stored in newsgroups. In particular, we study the network formed by cross-posts, messages that are posted to two or more newsgroups simultaneously. We ...
Christos Gkantsidis, Milena Mihail, Amin Saberi
International Conference on Measurements and Modeling of Computer Systems, SIGMETRICS 2003, 2003 – SIGMETRICS
It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to ...