Publications

A (5/3+ε)-approximation for strip packing. Rolf Harren, Klaus Jansen, Lars Prädel, Rob van Stee. Proc. WADS 2011, LNCS 6844, 475-487, 2011.
A truthful constant approximation for maximizing the minimum load on related machines. Giorgos Christodoulou, Annamária Kovács, Rob van Stee. Proc. WINE 2010, LNCS 6484, 182-193, 2010.
An improved algorithm for online rectangle filling. Rob van Stee. Proc. WAOA 2010, LNCS 6534, 249-260, 2011. To appear in Theoretical Computer Science.
Max-min online allocations with a reordering buffer. Leah Epstein, Asaf Levin, Rob van Stee. SIAM Journal on Discrete Mathematics 25:1230-1250, 2011. Also in Proc. ICALP 2010, LNCS 6198, 336-347, 2010.
Maximizing the minimum load: the cost of selfishness. Leah Epstein, Elena Kleiman, Rob van Stee. Proc. WINE 2009, LNCS 5929, 232-243, 2009.
On the price of stability for undirected network design. George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, Rob van Stee. Proc. WAOA 2009, LNCS 5893, 86-97, 2009.
Improved absolute approximation ratios for two-dimensional packing problems. Rolf Harren, Rob van Stee. Proc. APPROX 2009, 177-189, 2009.
Packing rectangles into 2OPT bins using rotations. Rolf Harren, Rob van Stee. Proc. SWAT 2008, LNCS 5124, 306-318, 2008. To appear in Journal of Scheduling.
Online unit clustering: variations on a theme. Leah Epstein, Asaf Levin und Rob van Stee. Theoretical Computer Science, 407:85-96, 2008.
The price of anarchy on uniformly related machines revisited. Leah Epstein, Rob van Stee. Proc. SAGT 2008, LNCS 4997, 46-57, 2008. To appear in Information and Computation.
Maximizing the minimum load for selfish agents. Leah Epstein, Rob van Stee. Theoretical Computer Science 411(1): 44-57, 2010. Also in Proc. LATIN 2008, LNCS 4957, 264-275, 2008.
Approximation schemes for packing splittable items with cardinality constraints. Leah Epstein, Rob van Stee. Proc. WAOA 2007, LNCS 4927, 232-245, 2008. Journal version with Asaf Levin and improved results to appear in Algorithmica.
On the online unit clustering problem. Leah Epstein, Rob van Stee
ACM Transactions on Algorithms 7(1), Article 7, 2010. Also in Proc. WAOA 2007, LNCS 4927, 193-206, 2008.
A monotone approximation algorithm for scheduling with precedence constraints. Sven O. Krumke, Anne Schwahn, Rob van Stee und Stephan Westphal. Operations Research Letters 36:247-249, 2008.
Two-dimensional packing with conflicts. Leah Epstein, Asaf Levin, Rob van Stee. Acta Informatica 45(3):155-175, 2008. Preliminary version (as 'Multi-dimensional...') in Proc. 16th FCT, LNCS 4639, 288-299, 2007
Preemptive scheduling on selfish machines. Leah Epstein, Rob van Stee. Proc. CAAN 2007, LNCS 4852, 57-70, 2007
Improved results for a memory allocation problem. Leah Epstein, Rob van Stee. Theory of Computing Systems 48(1):79-92, 2011. Also in Proc. 10th WADS, LNCS 4619, 362-373, 2007.
Bounds for online bounded space hypercube packing. Leah Epstein, Rob van Stee. Discrete Optimization 4(2):185-197, 2007.
Calculating lower bounds for caching problems. Leah Epstein, Rob van Stee. Computing 80(3):275-285, 2007.
Paging with connections: FIFO strikes again. Leah Epstein, Yanir Kleiman, Jiri Sgall, Rob van Stee. Theoretical Computer Science 377:55-64, 2007
Paging with request sets. Leah Epstein, Rob van Stee and Tami Tamir. Theory of Computing Systems 44(1):67-81, 2009. Also in Proc. 10th SWAT, LNCS 4059, 124-135, 2006
Speed Scaling of Tasks with Precedence Constraints. Kirk Pruhs, Rob van Stee, Patchrawat Uthaisombut. Proc. 3rd WAOA, LNCS 3879, 307-319, 2005. Theory of Computing Systems 43(1): 67-80 (2008)
Optimal online algorithms for multidimensional packing problems. Leah Epstein, Rob van Stee. SIAM Journal on Computing 35(2):431-448, 2005. This paper combines results from our papers in SODA 2004 and ESA 2004 listed below.
Online square and cube packing. Leah Epstein, Rob van Stee. Acta Informatica 41(9):595-606, 2005.
On strip packing with rotations. Klaus Jansen, Rob van Stee
STOC '05 Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, 2005
Combining request scheduling with web caching. Tomás Feder, Rajeev Motwani, Rina Panigrahy, Steve Seiden, Rob van Stee, An Zhu. Theoretical Computer Science 324(2-3):201-218, 2004. Special issue in memoriam of Steve Seiden.
An approximation algorithm for square packing. Rob van Stee. Operations Research Letters 32(6):535-539, 2004
This side up! Leah Epstein, Rob van Stee
ACM Transactions on Algorithms (TALG), 2006. Also in Proc. 2nd WAOA (2004), LNCS 3351, 48-60
Online bin packing with resource augmentation. Leah Epstein, Rob van Stee. Discrete Optimization 4:322-333, 2007. Also in Proc. 2nd WAOA (2004), LNCS 3351, 23-35
On variable-sized multidimensional packing. Leah Epstein, Rob van Stee. Proc. of 12th ESA (2004), 287-298.
Online scheduling of splittable tasks. Leah Epstein, Rob van Stee
ACM Transactions on Algorithms 2(1):79-94, 2006. A preliminary version appeared under the title "Online scheduling of splittable tasks in peer-to-peer networks" in Proc. of 9th SWAT (2004), 408-419.
Optimal online bounded space multidimensional packing. Leah Epstein, Rob van Stee. Proc. of 15th SODA (2004), 207-216.
Improved competitive guarantees for QoS buffering. Alex Kesselman, Yishay Mansour, Rob van Stee. Algorithmica, 43(1--2):63--80, 2005. Special issue on network design. Also in Proc. of 11th ESA (2003), LNCS 2832, 361-372
A study of integrated document and connection caching. Susanne Albers, Rob van Stee. Algorithmica 47(3):239-252, 2007.. Also in Proc. of 30th ICALP (2003), LNCS 2719, 653-667
Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem. Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, Guo-Hui Lin, Rob van Stee. Journal of Scheduling 6(2):131-147, 2003
Minimizing the total completion time on a single on-line machine, using restarts. Rob van Stee, Johannes A. La Poutré. Journal of Algorithms 57(2):95--129, 2005. Also in Proc. 10th ESA (2002), LNCS 2461, 872-883
Minimizing the maximum starting time on-line. Leah Epstein, Rob van Stee. Information and Computation 195(1-2):53-65, 2004. Also in Proc. 10th ESA (2002), LNCS 2461, 449-460
More on weighted servers or FIFO is better than LRU. Leah Epstein, Csanad Imreh, Rob van Stee. Theoretical Computer Science 306(1-3):305-317, 2003. Also in Proc. of 27th MFCS (2002), LNCS 2420, 257-268
Preemptive scheduling in overloaded systems. Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomas Tichy, Nodari Vakhania. Journal of Computer and System Sciences, 67(1):183-197, 2003. Also in Proc. of 29th ICALP (2002), LNCS 2380, 800-811.
New bounds for variable-sized online bin packing. Steve Seiden, Rob van Stee, Leah Epstein. SIAM Journal on Computing 32(2):455-469, 2003. Also in Proc. of 29th ICALP (2002), LNCS 2380, 306-317
New bounds for multi-dimensional packing. Steve Seiden, Rob van Stee. Algorithmica 36(3):261-293, 2003. Also in Proc. of 13th SODA (2002), 486-495
Lower bounds for on-line single-machine scheduling. Leah Epstein, Rob van Stee. Theoretical Computer Science 299(1-3): 439-450, 2003. Also in Proc. of 26th MFCS (2001), LNCS 2136, 338-350
Running a job on a collection of dynamic machines, with on-line restarts. Rob van Stee, Johannes A. La Poutré. Acta Informatica 37(10):727-742, 2001
Optimal on-line flow time with resource augmentation. Leah Epstein, Rob van Stee. Discrete Applied Mathematics 154(4):609-692, 2006. Also in Proc. of 13th FCT (2001), LNCS 2138, 472-482. This paper was presented at the WEA workshop.
Partial servicing of on-line jobs. Rob van Stee, Johannes A. La Poutré. Journal of Scheduling 4(6):379-396, 2001 (Special Issue on Efficient Scheduling Algorithms). Also in Proc. of 3rd APPROX (2000), LNCS 1913, 250-261.
Resource augmentation in load balancing. Yossi Azar, Leah Epstein, Rob van Stee. Journal of Scheduling 3(5):249-258, 2000. (Special issue on Approximation Algorithms). Also in Proc. of 7th SWAT (2000), LNCS 1851, 189-199.