Georgia Institute of Technology, Atlanta
Journal of the ACM, vol. 48,no. 2,2001 – JACM
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m logm) ...
The Internet, which isintrinsically a common playground for a large number of players with varying degrees of collaborative and sel sh motives, naturally gives rise to numerous new game theoretic issues. Computational problems underlying
FOCS 1999: New York, 1999 – FOCS
We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log ...
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, 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 ...