Some of Cliff Stein's Papers

Some Recent Papers. (Links are under construction.)

Journal papers (since 2000)

Online Scheduling of Packets with Agreeable Deadlines. with J. Lukasz, F. Li and J. Sethuraman. In ACM Transactions on Algorithms . To appear.
FairTorrent: a Deficit-based Distributed Algorithms to Ensure Fairness in Peer-to-Peer Systems. with J. Nieh and A. Sherman. In IEEE/ACM Transcations on Networking . To appear.
Solving Maximum Flow Problems in Real World Bipartite Graphs. with S. Negruseri, M. Pasio, B. Stanley and C. Strat. In ACM Journal of experimental Algorithms 16, 2011.
Approximating Semidefinite Packing Programs. with G. Iyengar and D. Phillips. In SIAM J. on Optimization , 21(1): 231--268, 2011.
On distributing symmetric streaming computations. with J. Feldman, S Muthukrishnan, A. Sidiropoulos, and Z. Svitkina. In ACM Transactions on Algorithms 6(4), 2010.
An O(n^5/2) Algorithm for the Rectilinear Minimum Link-Distance Problem in Three Dimensions. with R Drysdale and D. Wagner. In Computational Geometry, Theory and Applications , 42(5): 376--387, 2010.
Bounded-space online bin cover. with E. Asgiersson. In J. Scheduling, 12:461--474, 2009.
Divide-and-Conqure Approximation Algorithm for Vertex Cover. with E. Asgiersson. In SIAM J. Discrete Math, 23:3, 1261--1280, 2009.
Speed Scaling for Weighted Flow Time. with N. Bansal and K. Pruhs. In SIAM J. Comp , 39(4): 1294-1308, 2009.
LP Decoding Corrects a Constant Fraction of Errors. with J. Feldman, R. Servedio, T. Malkin, M. Wainwright. In IEEE Transactions on Information Theory , 53(1): 82-89, 2007.
In Rounding Algorithms for a Geometric Embedding Relaxation of Minimum Multiway Cut. with D. Karger, P. Klein, M. Thorup, N. Young. In Math of OR , 29(3), pp. 436--461, 2004.
Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs. with S. Kolliopoulos. In Mathematical Programming , 99, 2004.
In Optimal Time Critical Scheduling via Resource Augmentation. with C. Phillips, E. Torng, and J. Wein. In Algorithmica , 32, 2002.
In Approximation Algorithms for Single-Source Unsplittable Flow. with S. Kolliopoulos. In SIAM J. Computing , 31(3):919-946, 2002.
Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling. with C. Bailey-Kellog, B. Donald, and J. Kelley. In Journal of Computational Biology , 8(1):19-36, 2001.
Approximation Techniques for Average Completion Time Scheduling. with C. Chekuri, R. Motwani, and B. Natarajan. In SIAM J. Computing , 31(1):146-166, 2001

Conference Articles (since 2000)

Multicast Routing for Energy Minimization Using Speed Scaling. with Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan and Kirk Pruhs. In Proceedings of the 1st Mediteranian Conference on Algorithms, 2012.
How to Schedule When You Have to Buy Your Energy. with K. Pruhs. In Proceedings of APPROX-RANDOM 2010 pp. 352-365, 2010.
Online Stochastic Packing Applied to Display Ad Allocation. with J. Feldman, M. Henzinger, N. Korula, V. . Mirrokni. In Proceedings of European Symposium on Algorithms pp. 182--194, 2010.
Feasible and accurate algorithms for covering semidefinite programs. with G. Iyengar and D. Phillips. In Proceedings of SWAT 2010 , pp. 150--162, 2010.
Adding Trust to P2P Distribution of Paid Content. with A. Sherman, A. Stavrou, J. Nieh, and A. Keromytis. In the proceedings of Information Security, 12th International Conference , 459-474, 2009.
Solving Maximum Flow Problems on Real World Bipartite Graphs. with S. Negruseri, M. Pasio, B. Stanley, and C. Strat. In the proceedings of 8th Workshop on Experimenta. Algorithms , 2009}
Asymptotic Performace of Non-Forced Idle Time Scheduling Policies in the Presence o. with ariable Demand for Resources. with A. Radovanovic. In Proceedings of Allerton Conference, 2008
On distributing symmetric streaming computations. with J. Feldman, S. Muthukrishnan, A. Sidiropoulos, Z. Svitkina. In the proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms , 2008
Non-Preemptive Min-Sum Scheduling with Resource Augmentation. with N. Bansal, H. Chan, R. Khandekar, K. Pruhs, and B. Schieber. In Proceedings of 48th Annual IEEE Symposium on the Foundations of Computer Science , 2007.
Vertex Cover Approximations on Random Graphs with E. Asgeirsson. In the proceedings of 6th Workshop on Experimental Algorithms , 2007.
Budget Optimization in Search-Based Advertising Auctions. with J. Feldman, S. Muthukrishnan and M. Pal. In the proceedings of the 8th ACM Conference on Electronic Commerce , 2007.
Speed Scaling for Weighted Flow Time. with N. Bansal and K. Pruhs. In the proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms , 2007
Better Online Buffer Management. with F. Li and J. Sethuraman. In the proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms , 2007.
Grouped Distributed Queues: Distributed Queue, Proportional Shar. with ultiprocessor Scheduling. with B. Caprita and J. Nieh. In Proceedings of Twenty Fifth Annual ACM SIGACT SIGOPS Symposium on the Principles of Distributed Computing , 2006.
Using Markov Chains to Design Algorithms for Bounded Space on-line Bin Cover. with E. Asgiersson. In Proceedings of Workshop on Algorithm Engineering and Experimentation , 2006.
An $O(n^{5/2} log n)$ algorithm for the Rectilinea. with inimum Link Distance Problem. with S. Drysdale and D. Wagner. {In Proceedings of the Canadian Conference on Computational Geometry , 2005.
Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring. with G. Iyengar and D. Phillips. In the proceedings of Eleventh Symposium on Integer Programming and Combinatorial Optimization , 2005.
Vertex Cover Approximation: Experiments and Observations. with E. Asgiersson. In the proceedings of 4th Workshop on Experimental Algorithms , 2005.
Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems. with B. Caprita, W.C. Chan, J. Nieh and H. Zheng. In the proceedings of the USENIX 2005 Annual Technical Conference , 2005.
An optimal on-line algorithm for packet scheduling with agreeable deadlines. with F. Li and J. Sethuraman. In the proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms , 2005.
LP Decoding Achieves Capacity. with J. Feldman. In the proceedings of 16th ACM-SIAM Symposium on Discrete Algorithms , 2005.
On the Capacity of Secure Network Coding. with J. Feldman, R. Servedio, T. Malkin. In proceedings of Allerton Conference, 2004.
LP Decoding Corrects a Constant Fraction of Errors. with J. Feldman, R. Servedio, T. Malkin, M. Wainwright. In proceedings of IEEE International Symposium on Information Theory , 2004.
Scheduling An Industrial Production Facility. with E. Asgiersson, J. Berry, C. Phillips, D. Phillips and J. Wein. In proceedings of Tenth Symposium on Integer Programming and Combinatorial Optimization , 2004.
Minimizing Makespan for the Lazy Bureaucrat Problem. with C. Hepner. In the proceedings of Scandinavian Workshop onAlgorithms and Theory , 2002.
Existence Theorems, Lower Bounds and Algorithms for Scheduling t. with eet Two Objectives. A. Rasala, E. Torng, and P. Uthaisombut. In the proceedings of 13th ACM-SIAM Symposium on Discrete Algorithms , 2002}
Scheduling Multi-Task Agents. with D. Rus and R. Zie. In proceedings of Fifth IEEE International Conferenc. on Mobile Agents , 2001
Approximation Algorithms for the Minimum Bends Travelin. with alesman Problem. D. Wagner. In proceedings of Eighth Symposium on Integer Programming and Combinatorial Optimization , 2001
Implementation of a PTAS for scheduling with release dates. with C. Hepner. In Proceedings of Workshop on Algorithm Engineering and Experimentation , 2001.
. with Clustering Data Without Prior Knowledge. J. Aslam and A. Leblanc. In Proceedings of Workshop on Algorithm Engineering , 2000
Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling. C. Bailey-Kellog, J. Kelley, B. Donald. In Proceedings of Intelligent Systems for Molecular Biology , 2000

If a paper you want does not appear here, please email me

Scheduling

Improved Bicriteria Existence Theorems for Scheduling Problems

with J. Aslam, A. Rasala and N. Young. In SODA 99.

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates

with F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, M. Sviridenko. In FOCS 99.

Scheduling Algorithms

with David Karger and Joel Wein, a chapter written for the CRC Handbook on Algorithms, 1997.

Optimal Time Critical Scheduling Via Resource Augmentation

with Cindy Phillips, Eric Torng and Joel Wein, 1997. To appear in Algorithm.s A preliminary version appeared in STOC 97.

Approximation Techniques for Average Completion Time Scheduling

with C. Chekuri, R. Motwani and B. Natarajan. To appear in SIAM J. Computing. Initial version appeared in Proceedings of SODA '97.

On the Existence of Schedules that are Near-Optimal for both Makespan and Total Weighted Completion Time

with Joel Wein. In OR Letters, 21, 1997.

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem

with Soumen Chakrabarti, Cindy Phillips, Andreas Schulz, David Shmoys and Joel Wein. In Journal of Combinatorial Optimzation, 1, 1998.

Improved Scheduling Algorithms for Minsum Criteria

with Soumen Chakrabarti, Cindy Phillips, Andreas Schulz, David Shmoys and Joel Wein, 1995. In Proceedings of ICALP '96.

Minimizing Average Completion Time in the Presence of Release Dates

with Cindy Phillips and Joel Wein, 1995. In Mathematical Programming B, 82, 1998. A Preliminary version appeared in WADS '95.

Job Scheduling in Rings

with Perry Fizzano, David Karger and Joel Wein. In Journal of Parallel and Distributed Computation, 34:2, 1997. A preliminary version appeared in SPAA '94.

Task Scheduling in Networks

with Cindy Phillips and Joel Wein, 1995. In SIAM Journal on Discrete Mathematics, 10:4, 1997.. (Preliminary version appeared in SWAT '94)

Improved Approximation Algorithms for Shop Scheduling Problems

with David Shmoys and Joel Wein, SIAM J. Computing, 23, pp. 617-632, 1994. (Preliminary version appeared in SODA 91)

Multicommodity Flow

An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow

with A. Goldberg, J. Oldham, and S. Plotkin. In IPCO 98.

Experimental evaluation of approximation algorithms for single-source unsplittable flow

with S. Kolliopoulos. In IPCO 99.

Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs

with Stavros Kolliopoulos. In Proceedings of IPCO 98.

Improved Approximation Algorithms for Unsplittable Flow Problems

with Stavros Kolliopoulos. To appear in SIAM J. Computing. Initial version appeared in Proceedings of FOCS 97.

A description of a recent implementation of a combinatorial minimum cost multicommodity flow algorithm, done jointly with Andrew Goldberg, Jeffrey Oldham and Serge Plotkin can be found here

Implementation of a Combinatorial Multicommodity Flow Algorithm,

with Tishya Leong and Peter Shor. In DIMACS Series in Discrete Mathenatics and Theoretical Computer Science: The First DIMACS IMplementation Challenge: Network Flows and Matchings, D. Johnson aand C. McGoech, ed. , 1993

Fast Approximation Algorithms for Multicommodity Flow Problems

with Tom Leighton, Fillia Makedon, Serge Plotkin, Eva Tardos, and Spyros Tragoudas, Journal of Computer and System Sciences, 50, 228-243, 1995. Preliminary version appeared in STOC '91

Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts

with Philip Klein, Serge Plotkin and Eva Tardos. SIAM J. Computing, 23, pp. 466-487, 1994. (Preliminary version appeared in STOC '90)

Minimum Cut Problem

MINIMUM CUT IMPLEMENTATION PAPER. A long (135 pages) preliminary version of Experimental Study of Minimum Cut Algorithms

with Chandra Chekuri, Andrew Goldberg, David Karger and Matthew Levine, 1996 can be found here. Comments are welcome. You can also find another (long) version of this work as Matt Levine's masters thesis at MIT. The version (10 pages) which appeared in the proceedings of SODA97 can be found here.