Deeparnab Chakrabarty

Office:
2210 KACB, College of Computing
Atlanta, Georgia 30318
Phone: (404)385-2270
Email: deepc [at] cc.gatech.edu

Research

Research Interests: Approximation Algorithms, Combinatorial Optimization, Algorithmic Game Theory
Adviser: Prof. Vijay V. Vazirani
Resume:(pdf) (As of January, 2008)

Preprints
On the Approximability of Budgeted Allocations and
Improved Lower Bounds for Submodular Welfare Maximization and GAP (with Gagan Goel)
(pdf)

Publications
New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem. (with Nikhil Devanur and Vijay Vazirani)
To appear in IPCO 2008
(conf-version)

On Competitiveness in Uniform Utility Allocation Markets. (with Nikhil Devanur)
Proceedings of WINE 2007
(conf-version)(full-version)

Public Advertisement Broker Markets. (with Atish Das Sarma and Sreenivas Gollapudi)
Proceedings of WINE 2007
(conf-version)

New Results on Rationality and Strongly Polynomial Time Solvability in Eisenberg-Gale Markets (with Nikhil Devanur and Vijay Vazirani)
Proceedings of WINE 2006
(conf-version) (full-version)

Design is as easy as Optimization (with Aranyak Mehta and Vijay Vazirani)
Proceedings of ICALP 2006
(conf-version)(full-version)

Fairness and Optimality in Congestion Games (with Aranyak Mehta, Viswanath Nagarajan and Vijay Vazirani)
Proceedings of EC 2005
(conf-version)

Manuscripts
An Alternate Proof of Nash-Williams-Tutte Theorem via Max-min Spanning Trees
(pdf)

Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. (with Yunhong Zhou and Rajan Lukose)
Appeared in 3rd Worskhop on Sponsored Search Auctions, 2007 held in conjunction with WWW2007.
(pdf)

Personal
Crosswords (1) (2)
Word Pyramids (link)

Last Modified on :