---

Online Research Publications

---

• Competitive online scheduling for server systems (pdf) A survey of competitive online scheduling that I wrote for stochastic scheduling researchers that tries to explain my view of online scheduling.

• Speed Scaling for Weighted Flow (with Nikhil Bansal, and Cliff Stein) SODA 2007 (pdf)

• Balanced Allocations of Cake (with Jeff Edmonds) FOCS 2006. (pdf)

• Algorithmic Problems in Power Management (with Sandy Irani)  Survey of my most recent research SIGACT News (ps, pdf)

• Cake cutting really is not a piece of cake (with Jeff Edmonds), SODA, 2006 (ps, pdf)

• Speed scaling of tasks with precedence constraints (with Rob van Stee and Patchrawat Uthaisombut), WAOA, 2005. (pdf)

• Speed scaling to manage temperature (with Nikhil Bansal), STACS 2005, (ps, pdf)

• Dynamic speed scaling to manage energy and temperture (with Nikhil Bansal and Tracy Kimbrel),  FOCS 2004, (ps, pdf)

• Online Scheduling (with Jiri Sgall and Eric Torng) A survey for the Handbook on Scheduling. (ps)

• The Multicast Pull Advantage in Dissemination-based Data Delivery ( with Jonathan Beaver,  Panos K. Chrysanthis, Vincenzo Liberatore) Hellenic Data Management Symposium 2004 (pdf).

• Getting the best response for your erg (with Patchrawat Uthaisombut and Gerhard Woeginger), SWAT 2004  (ps). Mathematica Animation

• Scalable data dissemination: what's hot and what's not (with Jonathan Beaver, Nicholas Morsillo, Panos Chrysanthis and Vincenzo Libertore) WebDB 2004 (ps).

• Approximation schemes for a class of subset selection problems (with Gerhard Woeginger) LATIN 2004 (pdf) To appear in a special issue of Theoretical Computer Science devoted to selected papers from LATIN 2004.

• A constant approximation algorithm for sorting buffers (with Jens Kohrt) LATIN 2004 (pdf)

• Server scheduling in the weighted l_p norm (with Nikhil Bansal) LATIN 2004 (pdf)

• A Maiden Analysis of Longest Wait First (with Jeff Edmonds) SODA 2004. (pdf )

• Semi-clairvoyant Scheduling. (with Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela),  ESA 2003 (ps).

• Server Scheduling in the L_p Norm: A Rising Tide Lifts All Boats, (with Nikhil Bansal), STOC 2003.  (ps version)

• An Optimized Multicast Based Data Dissemination Middleware, (with Jonathan Beaver, Wei Li, Vince Penkrot, Siddhartha Roychowdhury, Mohamed Sharaf, Wenhui Zhang, Panos Chrysanthis, and Vincenzo Liberatore), IEEE International Conference on Data Engineering (ICDE) 2003.  (pdf version)

• Middleware support for multicast-based data dissemination: a working reality, (with Panos Chrysanthis and Vincenzo Liberatore), IEEE Workshop on Reliable Dependable Systems (WORDS) 2003.  (pdf version)

• A comparison of multicast pull models (with Patchrawat Uthaisombut), ESA 2002.  (ps version) .

• Multicast pull scheduling: when fairness is fine, (with Jeff Edmonds), SODA 2002. (ps version) , (pdf version) .

• Evaluating the Local Ratio Algorithm for Dynamic Storage Allocation (with Eric Wiewiora), ALENEX 2002 (ps version) .

• Online weighted flow time and deadline scheduling , (with Luca Becchetti, Stefano Leonardi and Alberto Marchetti-Spaccamella), APPROX 2001.

• Scheduling broadcasts in wireless networks , (with Bala Kalyanasundaram, and Mahe Velauthapillai),  special issue of  Journal of Scheduling devoted to selected papers from the 2000 European Symposium on Algorithms .

• Dynamic spectrum allocation: The impotency of duration notification . (with Bala Kalyanasundaram), Journal of Scheduling .

• Caching for web searching (with Bala Kalyanasundaram, John Noga, and Gerhard Woeginger), special issue of Algorithmica devoted to internet algorithmics.

• Eliminating migration in multi-processor scheduling , (with Bala Kalyanasundaram), special issue of Journal of Algorithms devoted to selected papers from the 1999 ACM/SIAM Symposium on Discrete Algorithms.

• Maximizing job completions online , (with Bala Kalyanasundaram), special issue of  Journal of Algorithms devoted to selected papers from the 1998 European Symposium on Algorithms.

• Errata: A new algorithm for scheduling periodic real-time tasks (with Bala Kalyanasundaram and Eric Torng),  Algorithmica, 2000.

• Minimizing flow time nonclairvoyantly (with Bala Kalyanasundaram), Journal of the ACM 2003.

• Fault-tolerant real-time scheduling , (with Bala Kalyanasundaram), Special issue of Algorithmica devoted to selected papers from the 1997 European Symposium on Algorithms.

• Speed is as powerful as clairvoyance , (with Bala Kalyanasundaram),  Journal of the ACM,  2000.

• Fault-tolerant scheduling , (with Bala Kalyanasundaram), SIAM Journal of Computing .

• On-line load balancing of temporary tasks , (with Y. Azar, B. Kalyanasundaram, S. Plotkin, and O. Waarts) Journal of Algorithms , 1997.

• Online network optimization problems , (with Bala Kalyanasundaram), Online Algorithms: The State of the Art , eds. A. Fiat and G. Woeginger, Lecture Notes in Computer Science 1442, Springer-Verlag, 1998. (Survey Paper)

• An optimal deterministic algorithm for online b-matching , (with Bala Kalyanasundaram),  Theoretical Computer Science,2000. To see how this relates the Google Ad-words problem, see this SIAM News article.

• The online transportation problem , (with Bala Kalyanasundaram),  SIAM Journal of Discrete Math , 2000.

• Constructing competitive tours from local information , (with Bala Kalyanasundaram), Special issue on dynamic and on-line algorithms of Theoretical Computer Science ,  1994.

• Not all insertion methods yield constant approximate tours in the Euclidean plane , (with Bala Kalyanasundaram), Theoretical Computer Science ,  1994.

• Online weighted matching , (with Bala Kalyanasundaram), Journal of Algorithms,  1993.