Publikationen / Publications

SIGACT news columns, Rob van Stee

Buffer minimization with conflicts on a line, Felix Höhne, Rob van Stee. FAW 2020: 62-73

The optimal absolute ratio for online bin packing, János Balogh, József Békési, György Dósa, Jiří Sgall, Rob van Stee. J. Comput. Syst. Sci. 102: 1-17, 2019. Also in Proc. SODA 2015, 1425-1438.

The price of clustering in bin-packing with applications to bin-packing with delays, Yossi Azar, Yuval Emek, Rob van Stee, Danny Vainstein. SPAA 2019: 1-10

Multidimensional packing problems, Leah Epstein, Rob van Stee. Handbook of Approximation Algorithms and Metaheuristics (1) 2018: 553-570

A two-phase algorithm for bin stretching with stretching factor 1.5 Martin Böhm, Jiří Sgall, Rob van Stee, Pavel Veselý. Journal of Combinatorial Optimization 34(3): 810-828, 2017.

Beating the harmonic lower bound for online bin packing. Sandy Heydrich and Rob van Stee. Proc. ICALP 2016.

Online algorithms with advice for bin packing and scheduling problems. Marc Renault, Adi Rosén and Rob van Stee. Theoretical Computer Science 600: 155-170, 2015.

Better algorithms for online bin stretching. Martin Böhm, Jiří Sgall, Rob van Stee, Pavel Veselý. Proc. WAOA 2014, LNCS 8952, 23-34, 2015. Journal version Online bin stretching with three bins Journal of Scheduling 20(6): 601-621, 2017.

The cost of selfishness for maximizing the minimum load on uniformly related machines. Leah Epstein, Elena Kleiman and Rob van Stee. Journal of Combinatorial Optimization 27(4): 767-777, 2014.

Dividing connected chores fairly. Sandy Heydrich and Rob van Stee. Theoretical Computer Science 593: 51-61, 2015. Also in Proc. SAGT 2013, LNCS 8146, 171-182, 2013.

Reordering buffer management with advice. Anna Adamaszek, Marc Renault, Adi Rosén, Rob van Stee. Journal of Combinatorial Optimization 20(5): 423-442, 2017. Also in Proc. WAOA 2013, LNCS 8447, 132-143, 2014.

A unified approach to truthful scheduling on related machines. Leah Epstein, Asaf Levin, Rob van Stee. Proc. SODA 2013, 1243-1252. SIAM, 2013. Mathematics of Operations Research 41(1): 332-351, 2016.

Real-time prefetching and caching. Peter Sanders, Johannes Singler und Rob van Stee. Journal of Scheduling 16(1): 47-58, 2013.

The price of anarchy for selfish ring routing is two. Xujin Chen, Benjamin Doerr, Xiaodong Hu, Weidong Ma, Rob van Stee, Carola Winzen. Transactions on Economics and Computation 2(2): Article 8, 2014. Also in Proc. WINE 2012, LNCS 7695, 420-433, 2012.

Online scheduling of jobs with fixed start times on related machines. Leah Epstein, Łukasz Jeż, Jiří Sgall, Rob van Stee. Algorithmica 74(1): 156-176, 2016. Also in Proc. APPROX 2012, LNCS 7408, 134-145, 2012.

A note on sorting buffers offline. Ho-Leung Chan, Nicole Megow, Rene Sitters, Rob van Stee. Theoretical Computer Science 423:11-18, 2012.

A (5/3+ε)-approximation for strip packing. Rolf Harren, Klaus Jansen, Lars Prädel, Rob van Stee. Computational Geometry: Theory and Applications 47(2): 248-267 (2014). Also in Proc. WADS 2011, LNCS 6844, 475-487, 2011.

A truthful constant approximation for maximizing the minimum load on related machines. George Christodoulou, Annamária Kovács, Rob van Stee. Theoretical Computer Science 489-490:88-98, 2013. Also in Proc. WINE 2010, LNCS 6484, 182-193, 2010.

An improved algorithm for online rectangle filling. Rob van Stee. Theoretical Computer Science 423:59--74, 2012. Also in Proc. WAOA 2010, LNCS 6534, 249-260, 2011.

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. Xujin Chen, Leah Epstein, Elena Kleiman, Rob van Stee. Theoretical Computer Science 482:9-19, 2013. Preliminary version without Xujin Chen and with partial results in 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.

Two for one: tight approximation of 2D bin packing. Rolf Harren, Klaus Jansen, Lars Prädel, Ulrich M. Schwarz, Rob van Stee. To appear in International Journal on the Foundations of Computer Science. Combined version of an independent paper by the middle three authors and Improved absolute approximation ratios for two-dimensional packing problems. Rolf Harren, Rob van Stee. Proc. APPROX 2009, 177-189, 2009.

Absolute approximation ratios for packing rectangles into bins. Rolf Harren, Rob van Stee. Journal of Scheduling 15:63-75, 2012. Also in Proc. SWAT 2008, LNCS 5124, 306-318, 2008 (as Packing rectangles into 2OPT bins using rotations.)

Online unit clustering: variations on a theme. Leah Epstein, Asaf Levin and Rob van Stee. Theoretical Computer Science, 407:85-96, 2008.

The price of anarchy on uniformly related machines revisited. Leah Epstein, Rob van Stee. Information and Computation 212:37-54, 2012. Also in Proc. SAGT 2008, LNCS 4997, 46-57, 2008.

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, Asaf Levin, Rob van Stee. Algorithmica 62(1-2): 102-129, 2012. Conference version without Asaf Levin and with partial results in Proc. WAOA 2007, LNCS 4927, 232-245, 2008.

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, Jiří 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, 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, Jiří 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.

On-line scheduling and bin packing. Ph.D. thesis, Leiden University, 2002.

Combinatorial algorithms for packing and scheduling problems. Habilitation thesis, Karlsruhe University, 2008.
Habilitation talk about electronic voting (in German).