Shuchi's publications

      Copyright notice
      Paper abstracts
      Shuchi's homepage


       UW CS
       Theory Group
       Theory Seminar

2009
• Region growing for multi-route cuts.
  With Siddharth Barman, arXiv:0908.0350. To appear at SODA'10.


• Sequential posted pricing and multi-parameter mechanism design.
  With Jason Hartline, David Malec, and Balu Sivan, arXiv:0907.2435.


• Pricing randomized allocations.
  With Patrick Briest, Robert Kleinberg, and S. Matthew Weinberg, arXiv:0904.2400. To appear at SODA'10.


• The price of anarchy of Bertrand games.
  With Feng Niu, EC'09.


• Packing Multiway Cuts in Capacitated Graphs. [extended abstract]
  With Siddharth Barman, SODA'09 and UW-Madison CS technical report 1642, Aug 2008. Also see the full version arXiv:0810.0674 here.


2008
• Bertrand Competition in Networks. [extended abstract]
  With Tim Roughgarden, SAGT'08.


2007
• Approximate Pricing via Virtual Valuations.
  With Jason Hartline and Bobby Kleinberg, EC'07. Also see the full (greatly improved) version arXiv:0808.1671 here.


2006
• Single Source Stochastic Routing.
  With Tim Roughgarden, APPROX'06.


• Optimal Cost Sharing Mechanisms for Steiner Forest Problems.
  With Mukund Sundararajan and Tim Roughgarden, WINE'06.


• Bayesian Optimal No-deficit Mechanism Design.
  With Jason Hartline, Uday Rajan and R. Ravi, WINE'06.


2005
• On the Utility of Privacy-Preserving Histograms.
  With Cynthia Dwork, Frank McSherry and Kunal Talwar, UAI'05.


• On the Hardness of Approximating Multicut and Sparsest-Cut. [extended abstract]
  With Robert Krauthgamer, Ravi Kumar, Yuval Rabani and D. Sivakumar, Computational Complexity (2006), 15(2): 94-114. Preliminary version appeared in CCC'05.


• Towards Privacy in Public Databases.
  With Cynthia Dwork, Frank McSherry, Hoeteck Wee and Adam Smith, TCC'05.


• Embeddings of Negative-type Metrics and An Improved Approximation to Generalized Sparsest Cut. [ps]
  With Anupam Gupta and Harald Racke, ACM Transactions on Algorithms, SODA 2005 Special Issue (2008), 4(2). Preliminary version appeared in SODA'05.


2004
• Approximation Algorithms for Deadline-TSP and Vehicle Routing with Time-Windows. [ps]
  With Nikhil Bansal, Avrim Blum and Adam Meyerson, STOC'04.


• Worst-case Payoffs of a Location Game. [ps]
  With Uday Rajan, R. Ravi and Amitabh Sinha, Operations Research Letters (2006), 34: 499-507. Preliminary version appeared as a poster in EC'04.


2003
• Approximation Algorithms for Orienteering and Discounted-Reward TSP. [ps]
  With Avrim Blum, David Karger, Terran Lane, Adam Meyerson and Maria Minkoff, SIAM Journal on Computing (2007), 37(2): 653-670. Preliminary version appeared in FOCS'03.


• Scaling Properties of the Internet Graph. [ps, extended abstract]
  With Aditya Akella, Arvind Kannan and Srinivasan Seshan, ACM SIGCOMM Computer Communication Review, Special Issue on Science of Network Design (July, 2004), 34(3): 43-56. Preliminary version appeared in PODC'03.


• Scheduling for Flow Time with Admission Control, or, How to Manage your To-Do List. [ps]
  With Nikhil Bansal, Avrim Blum and Kedar Dhamdhere, ESA'03. (A shorter version appeared in MAPSP'03.)


• Profit Maximizing Mechanisms for the Extended Multicasting Game. [ps]
  With David Kitchin, Uday Rajan, Ramamoorthi Ravi and Amitabh Sinha, poster session, EC'03.


• Online Oblivious Routing. [ps]
  With Nikhil Bansal, Avrim Blum and Adam Meyerson, SPAA'03.


2002
• Correlation Clustering. [ps, extended abstract]
  With Nikhil Bansal and Avrim Blum, Machine Learning, Special Issue on Clustering (2004), 56(1-3): 89-113. Preliminary version appeared in FOCS'02.


• Static Optimality and Dynamic Search Optimality in Lists and Trees. [ps]
  With Avrim Blum and Adam Kalai, Algorithmica, Special Issue on Online Algorithms (2003), 36: 249-260. Preliminary version appeared in SODA'02.


2001
• Learning from Labeled and Unlabeled Data using Graph Mincut. [ps]
  With Avrim Blum, ICML'01.


• QoS based Scheduling for Incorporating Variable Rate Coded Voice in BLUETOOTH. [ps]
  With Huzur Saran and Mitali Singh, ICC'01.

 

Technical Reports

• Bayesian Optimal No-deficit Mechanism Design. [ps]
  With Jason Hartline, R. Ravi and Uday Rajan. CMU-CS-04-153, Aug 2004.


• Scaling Properties of the Internet Graph.
  With Aditya Akella, Arvind Kannan and Srinivasan Seshan. CMU-CS-03-143, May 2003.


• Min-Max Payoffs of a Location Game.
  With Uday Rajan, R. Ravi and Amitabh Sinha. CMU-CS-03-141, May 2003.
  Also appeared as a short paper in ACM EC'04 and published in Operations Research Letters.


• Approximation Algorithms for Orienteering and Discounted-Reward TSP.
  With Avrim Blum, David Karger, Terran Lane, Adam Meyerson and Maria Minkoff. CMU-CS-03-121, March 2003.


• Profit Maximizing Mechanisms for the Extended Multicasting Game.
  With David Kitchin, Uday Rajan, Ramamoorthi Ravi and Amitabh Sinha. CMU-CS-02-164, July 2002.
  Also appeared as a short paper (poster) in ACM EC'03.


• Mechanisms for Internet Routing: A Study.
  With Aditya Akella and Srini Seshan. CMU-CS-02-163, July 2002.