Vijay V. Vazirani

Ph.D., University of California, Berkeley, 1983
S.B., Massachusetts Institute of Technology, 1979
Professor
College of Computing
Georgia Institute of Technology


A worthy cause: Akshaya Patra

My Picture

Research Interests

Design of efficient exact and approximation algorithms, algorithmic game theory,
computational complexity theory, algorithmic problems in coding theory.
Supported by NSF Grant CCF-0728640.

Books

Approximation Algorithms, Springer-Verlag, Berlin, 2001.
Preface, Table of Contents, and Chapter 1.

Translations:
Japanese
Polish
French

Algorithmic Game Theory, Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, editors,
Cambridge University Press, Cambridge, 2007.

Non-printable version on the web and DIMAP Workshop (Warwick University) introducing the book.


An interesting aside: A sampling of books written by my father.

Selected Recent Talks

Three talks on ``Polynomial Time Algorithms for Market Equilibria''
New Horizons in Computing, Spring School, Tokyo, Japan, February 2006.

1) History and Basic Notions
2) Combinatorial Algorithms for Traditional Market Models
3) New Market Models, Resource Allocation Markets



``New Market Models and Algorithms'' talk ppt
CS Colloquium, Harvard University, April 2006.
ACO Distinguished Lecture, April 2006.
Webcast from Microsoft Research, May 2006.


``Markets and the Primal-Dual Paradigm'' talk ppt
Keynote address, DIMAP Workshop, Warwick University, March 2007.
MS&E Colloquium (Distinguished lecture), Stanford University, May 2007.
Plenary talk, WINE, San Diego, December 2007.

Selected Recent Papers

Algorithms for Market Equilibria

  • ``Continuity Properties of Equilibria in Some Fisher and Arrow-Debreu Market Models'', with L. Wang, submitted 2008.

  • ``Continuity Properties of Equilibrium Prices and Allocations in Linear Fisher Markets'', with N. Megiddo, WINE 2007.

  • ``Spending Constriant Utilities, with Applications to the Adwords Market'', submitted, 2006.

  • ``New Results on Rationality and Strongly Polynomial Solvability in Eisenberg-Gale Markets'', with D. Chakrabarty and N. Devanur, WINE 2006.

  • ``Eisenberg-Gale Markets: Algorithms and Game-Theoretic Properties'', with K. Jain, STOC 2007.

  • ``Market equilibria for homothetic, quasi-concave utilities and economies of scale in production'', with K. Jain and Y. Ye, SODA 2005.

  • ``An Auction-Based Market Equilibrium Algorithm for a Production Model'', with S. Kapoor and A. Mehta, WINE 2005.

  • ``The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness Results'', with N. Devanur, STOC 2004.

  • ``An Auction-Based Market Equilbrium Algorithm for the Separable Gross Substitutibility Case'', with R. Garg and S. Kapoor, APPROX 2004.

  • ``An Improved Approximation Scheme for Computing Arrow-Debreu Prices for the Linear Case'', with N. Devanur, Proc. FSTTCS 2003.

  • ``Rate Control as a Market Equilibrium'', with F. P. Kelly, unpublished note (2002).

  • ``Market Equilibrium via a Primal-Dual Algorithm for a Convex Program'', with N. Devanur, C. Papadimitriou, and A. Saberi, to appear in Journal of ACM.

    Other Recent Papers

    1. ``New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem'', with D. Chakrabarty and N. Devanur, IPCO 2008.

    2. ``Solvency Games'', with N. Berger, N. Kapur, and L. Schulman, 2007.

    3. ``Design is as Easy as Optimization'', with D. Chakrabarty and A. Mehta, ICALP 2006.

    4. ``Adwords and Generalized Online Matching'', with A. Mehta, A. Saberi and U. Vazirani, Journal of ACM 54(5), 2007.
      Press release by Georgia Tech and a SIAM News article by Sara Robinson on this work.

    5. ``Diversity in Times of Adversity: Probabilistic Strategies in Microbial Survival Games'', with D. Wolf and A. Arkin, Journal of Theoretical Biology, vol. 234, 2005.
      Reviewed in Faculty of 1000.

    6. ``A Microbial Modified Prisoner's Dilemma Game: How Frequency-Dependent Selection can Lead to Random Phase Variation'', with D. Wolf and A. Arkin, Journal of Theoretical Biology, vol. 234, 2005.

    7. ``On the Capacity of Multiple Unicast Sessions in Unidrected Networks'', with K. Jain, R. Yeung and G. Yuval, ISIT 2005.

    8. ``Improved Simulated Annealing Algoirthm for the Permanent and Combinatorial Counting Problems'', with I. Bezakova, D. Stefankovic and E. Vigoda, SIAM Journal of Computing, 37(5) (2008) 1429 -1454.

    9. ``Profit-Maximizing Multicast Pricing by Approximating Fixed Points'', with A. Mehta and S. Shenker, J. of Algorithms, 58(2) (2006), 150-164.

    10. ``Randomized Truthful Auctions of Digital Goods are Randomizations over Truthful Auctions'', with A. Mehta, Proc. EC 2004.

    11. ``A stochastic process on the hypercube with applications to peer-to-peer networks'', with M. Adler, E. Halperin, and R. M. Karp, Proc. STOC 2003.

    12. ``Equitable Cost Allocations via Primal-Dual-Type Algorithms'', with K. Jain, SIAM Journal of Computing, 38(1) (2008) 241-256.

    13. ``Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP'', with K. Jain, M. Mahdian, E. Markakis, and A. Saberi, Journal of ACM, 50(6) (2003), 795-824.

    14. ``A computationally motivated definition of parametric estimation and its applications to the Gaussian distribution'', with L. J. Schulman, Combinatorica 25(4) (2005) 465-486.

    15. ``Applications of Approximation Algorithms to Cooperative Games'', with K. Jain, Proc. STOC 2001.

    16. ``Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation'', with K. Jain, Journal of ACM, Vol. 48 (2001) 274-296.

    17. ``A Graph Theoretic Approach to Software Watermarking'', with R. Venkatesan and S. Sinha, 4th International Information Hiding Workshop, Pittsburgh (2001).

    18. ``Recent Results on Approximating the Steiner Tree Problem and its Generalizations'', Theoretical Computer Science, Vol. 235, (2000) 205-216.

    19. ``A New Heuristic for Rectilinear Steiner Trees'', with I. Mandoiu and J. L. Ganley, IEEE Transactions on CAD, Vol.19, No. 10 (2000) 1129-1139.

    Other Selected Papers

      Click here

    Recent and Current Ph.D. Students

      Kamal Jain
      Ion Mandoiu
      Amin Saberi
      Aranyak Mehta
      Nikhil R. Devanur
      Deeparnab Chakrabarty
      Gagan Goel
      Chinmay Karande

    Conference Committees and Workshops


      Computational Issues in Game Theory and Mechanism Design, DIMACS, October 2001.

      APPROX 2002, Rome, Italy, September 2002.

      ACM Conference on Electronic Commerce (EC'03) San Diego, California, June 2003.

      ICALP 2003 Eindhoven, The Netherlands, July 2003.

      Algorithmic Game Theory and the Internet Schloss Dagstuhl, Germany, July 2003.

      Workshop on the Interface between Biology and Game Theory DIMACS, Rutgers, April 2004.

      First Bertinoro Workshop on Algorithmic Game Theory Bertinoro, Italy, July 2004.

      Workshop on Internet and Network Economics Hong Kong, Dec 2005.

      APPROX 2006 Barcelona, Spain, August 2006.

      COCOON Taipei, Taiwan, August 2006.

      Workshop on Internet and Network Economics Patra, Greece, Dec 2006.

      Workshops on the Computational Worldview and the Sciences:

      1). Princeton, NJ, December 11 and 12, 2006.
      2). Caltech, CA, March 15 and 16, 2007.

      Workshop on Internet and Network Economics San Diego, CA, Dec 2007.

      LATIN 2008 Rio de Janeiro, Brazil, April 2008.

      First International Workshop on Algorithmic Game Theory Paderborn, Germany, May 2008.

    College of Computing,
    KACB, Room 2142
    266 Ferst Drive
    Georgia Institute of Technology
    Atlanta, Georgia 30332-0765
    Phone: 404-894-5850
    vazirani AT cc DOT gatech DOT edu