Gagan Goel

  Postdoctoral Fellow
  School of Computer Science
  Georgia Institute of Technology.

  CV: pdf

   I completed my Ph.D. in Algorithms, Combinatorics, and Optimization at Georgia Tech in Aug 2009, under the supervision of Prof. Vijay Vazirani.
   During my Ph.D. study, I did internships at:
     - Google Research (Summer 08)
     - Yahoo! (Summer 07)
     - Amazon.com (Summer 06)
   Before that I was at Indian Institute of Technology, Delhi, where I completed my B.Tech in Computer Science and Engineering in Aug 2004.


  Research Interests:
   - Computational aspects of Economics and Game Theory, Algorithmic Mechanism Design, Auction Theory.
   - Algorithm Design, Approximation and Online Algorithms for Combinatorial Optimization Problems.


  Publications & Tech Reports:

  - Single-Parameter Combinatorial Auctions with Partially Public Valuations.
       To appear in SAGT, 10. with C. Karande and L. Wang.

  - A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for it.
      To appear in SAGT, 10. with V. Vazirani.

  - Budget-constrained Auctions with Heterogeneous Items.
       STOC, 10. with S. Bhattacharya, S. Gollapudi, and K. Munagala.

  - Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions .
       FOCS, 09. with C. Karande, P. Tripathi, and L. Wang.

  - Efficiency of Revenue-Optimal Mechanisms.
        EC,09. with Gagan Aggarwal and Aranyak Mehta.

  - On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP.
       FOCS, 08. with Deeparnab Chakrabarty.

  - Efficiency, Fairness, and Competitiveness in Nash Bargaining Games.
      WINE, 08. with Deeparnab Chakrabarty, Vijay Vazirani, Lei Wang and Changyuan Yu.

  - Online Budgeted Matching in Random Input Models with applications to Adwords.
      SODA, 08. with Aranyak Mehta.

  - Adwords Auctions with Decreasing Valuation Bids.
       WINE, 07. with Aranyak Mehta.

  - Towards Topology Aware Networks.
      INFOCOM, 07. with Milena Mihail, Amin Saberi, and Christos Gkantsidis.

  - Minimizing Flow Time on Related Machines.
      B.Tech Thesis, 2004. Thesis advisors: Naveen Garg, Amit Kumar.


   Working / Under Submission Papers

  - Online Vertex-weighted Bipartite Matching.
       Submitted, 10. with Gagan Aggarwal, Chinmay Karande, and Aranyak Mehta.

  - Truthfulness vs Approximability: An Irreconcilable conflict.
       Manuscript, 09. with L. Wang.

  - Algorithms for Auctions with Combinatorial Demand and Sellers with Discounted Price Functions.
       Manuscript, 09. with P. Tripathi and L. Wang.

  - Submodularity Helps in Nash and Non-symmetric Bargaining Games.
       Submitted, 09. with D. Chakrabarty, V. Vazirani, L. Wang, C. Yu.



  Selected Talks:

  - Algorithms for Multi-agent Combinatorial Problems with Submodular Cost Functions. Given at:
     - Univ. of Washington .
     - Stanford University.
     - Univ. of California, Berkeley.


  - Budgeted Allocations/Auctions with Budget Constraints. Given at:
     - Microsoft Research, Redmond.
     - Workshop on Approximation Algorithms and their Limitations at TTI-Chicago.
     - INFORMS 2009.
     - Google Research, Mountain View.
     - Georgia Tech ACO student seminar.


  - Efficiency of Revenue-Optimal Mechanisms. Given at:
     - Bellairs Workshop on Algorithmic Game Theory.
     - ISMP 2009.
     - NY Computer Science and Economics Day rump session 2008.



   Contact:
  - Email: gagang AT cc DOT gatech DOT edu
  - Office: Klaus 2116
  - Phone: 678-772-3352