Christine Chung's Research

Papers

Completion Time Scheduling and the WSRPT Algorithm, with Bo Xiong. ISCO 2012 (International Symposium on Combinatorial Optimization).

The power of fair pricing mechanisms, with Katrina Ligett, Aaron Roth, and Kirk Pruhs. Algorithmica, Nov 2011. (Earlier version appeared in LATIN 2010.)

SRPT is 1.86-competitive for completion time scheduling, with Tim Nonner and Alex Souza. SODA 2010 (ACM-SIAM Symposium on Discrete Algorithms).

Admission control mechanisms for continuous queries in the cloud, with Lory Al Moakar, Panos Chrysanthis, Shenoda Guirguis, Alexandros Labrinidis, Panayiotis Neophytou, and Kirk Pruhs. ICDE 2010 (IEEE International Conference on Data Engineering).

On the price of stability for undirected network design, with Giorgos Christodoulou, Katrina Ligett, Evangelia Pyrga, and Rob van Stee. WAOA 2009 (Workshop on Approximation and Online Algorithms).

Stochastic stability in internet router congestion games, with Evangelia Pyrga. SAGT 2009 (Symposium on Algorithmic Game Theory). For a more complete version of this work, see the relevant chapter of my thesis.

The price of stochastic anarchy, with Katrina Ligett, Kirk Pruhs and Aaron Roth. SAGT 2008 (Symposium on Algorithmic Game Theory).

The online transportation problem:  on the exponential boost of one extra server, with Kirk Pruhs and Patchrawat Uthaisombut. LATIN 2008 (Latin American Theoretical Informatics Symposium).

Presentations/talks

Expanding CS1: applications across the liberal arts

CCSCNE (Consortium for Computing Sciences in Colleges, Northeast Region), Hartford, CT, April 2010

The price of stochastic anarchy

SAGT in Paderborn, Germany, May 2008
MPII in Saarbrücken, Germany, May 2008
University of Freiburg in Freiburg, Germany, May 2008

Stochastically stable states in load balancing and congestion games

CMU Theory Lunch, May 2007
Computational Social Systems and the Internet at Dagstuhl, Germany, July 2007