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

My Picture
A worthy cause: Akshaya Patra

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 and ONR Grant N000140910755.

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 Papers

Algorithms for Markets and Bargaining

  • ``Nash Bargaining via Flexible Budget Markets'', submitted, 2009.

  • ``Some Computational and Game-Theoretic Issues in Nash and Nonsymmetric Bargaining Games'', with D. Chakrabarty, G. Goel, L. Wang and C. Yu, submitted, 2009.

  • ``Towards an Internet Connecrtivity Market'', with V. Valancius, S. Sundaresan, U. Hassan, N. Feamster and R. Johari, Georgia Tech report number: GT-CS-09-01 (2009).

  • ``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.

  • ``Eisenberg-Gale Markets: Algorithms and Game-Theoretic Properties'', with K. Jain, STOC 2007. To appear in Games and Economic Behavior.

  • ``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.

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

  • ``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, Journal of ACM, vol. 55(5) (2008).

    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, FSTTCS 2008.

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

    4. ``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.

    5. ``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.

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

    7. ``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.

    8. ``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.

    9. ``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.

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

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

    12. ``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.

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

    Other Selected Papers: Click here

    Selected Recent Talks

    Two talks for the algorithmically inclined on
    ``Combinatorial Algorithms for Convex Programs Capturing Market Equilibria and Nash Bargaining Solutions''
    Bellairs Workshop on Algorithmic Game Theory, Barbados, March 2009.

    1) Fisher Linear Markets
    2) Nash Bargaining


    ``Nash Bargaining via Flexible Budget Markets'' talk ppt
    Youtube, Google Research, September 2008.


    ``New Market Models and Algorithms'' talk ppt
    Webcast from Microsoft Research, May 2006.
    ACO Distinguished Lecture, April 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.

    Past and Present Ph.D. Students

      Mark Krentel
      Samir Khuller
      Naveen Garg
      Kamal Jain
      Ion Mandoiu
      Amin Saberi
      Aranyak Mehta
      Nikhil R. Devanur
      Deeparnab Chakrabarty
      Gagan Goel
      Lei Wang
      Chinmay Karande
      Pushkar Tripathi

    Some Memorable Workshops Co-organized


    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