Uni-Logo
Algorithms and Complexity
 

Publications

2008

  • T. Jacobs. On the complexity of optimal hotlink assignment. To appear in Proc. 15th Annual European Symposium on Algorithms (ESA), 2008.

  • S. Albers and S. Lauer. On List Update with Locality of Reference. In Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP '08), Springer LNCS 5125, pages 96-107, 2008.

  • S. Albers. On the value of coordination in network design. To appear in Proc. 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2008.

  • C. Gunia. Energy-efficient windows scheduling. To appear in Proc. 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Springer LNCS, 2008.

  • T. Jacobs. An experimental study of recent hotlink assignment algorithms. To appear in Proc. Workshop on Algorithm Engineering & Experiments (ALENEX) , 2008.

2007

  • T. Nonner, S. Krumke, P. Merz and K. Rupp. Distributed approximation algorithms for finding 2-edge-connected ssubgraphs. To appear in Proc. 11th International Conference on Principles of Distributed Systems (OPODIS), Springer LNCS, 2007.

  • M. Hoefer and A. Souza. Tradeoffs and average-case equilibira in selfish routing. In Proc. 15th Annual European Symposium on Algorithms (ESA), Springer LNCS 4698, 63-74, 2007.

  • S. Albers and T. Jacobs. An experimental study of new and known online packet buffering algorithms In Proc. 15th Annual European Symposium on Algorithms (ESA), Springer LNCS 4698, 754-765, 2007.

  • C. Gunia. Minimal range assignment for broadcasts. In Algorithms for Sensor and Ad Hoc Networks, Springer LNCS 4621, 215-236, 2007.

  • T. Jacobs. Constant factor approximations for the hotlink assignment problem. In Proc. 10th Workshop on Algorithms and Data Structures (WADS), Springer LNCS 4619, 188-200, 2007.

  • S. Albers and R. van Stee. An study of integrated document and connection caching in the WWW. Algorithmica, 47(3):239-252, 2007.

  • S. Albers, F. Müller and S. Schmelzer. Speed scaling on parallel processors. In Proc. 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'07), 289-298, 2007.

2006

  • P. Briest and C. Gunia. Energy-efficient broadcast scheduling for speed-controlled transmission channels. To appear in Proc. 7th International Symposium on Algorithms and Computation (ISAAC'06), 2006.

  • A. Souza. On adequate performance measures for paging. In Proc. 38th ACM Symposium on Theory of Computing (STOC'06), 487-496, 2006.

  • S. Albers, S. Eilts, E. Even-Dar, Y. Mansour and L. Roditty. On Nash equilibria for a network creation game. In Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA'06), 89-98, 2006.

  • S. Albers and Hiroshi Fujiwara. Energy-efficient algorithms for flow time minimization. In Proc. 23rd International Symposium on Theoretical Aspects of Computer Science (STACS'06), Springer LNCS 3884, 621-633, 2006.

  • C. Gunia. On broadcast scheduling with limited energy. In Proc. 6th Conference on Algorithms and Complexity (CIAC'06), Springer LNCS 3998, 151-162, 2006.

  • S. Albers. Online algorithms. In Interactive Computation: The New Paradigm edited by D.Q. Goldin, S.A. Smolka and P. Wegner, 143-164, 2006.

2005

  • S. Albers and M. Schmidt. On the performance of greedy algorithms in packet buffering. SIAM Journal on Computing, 35:278-304, 2005.

  • S. Albers, L.M. Favrholdt and O. Giel. On paging with locality of reference. Journal of Computer and System Sciences, 70:145-175, 2005.

  • S. Albers and M. Büttner. Integrated prefetching and caching in single and parallel disk systems. Information and Computation, 198:24-39, 2005.

  • M. Schmidt. Packet buffering: Randomization beats deterministic algorithms. In Proc. 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS'05), Springer LNCS 3404, 293-304, 2005.

  • S. Albers and H. Bals. Dynamic TCP acknowledgment: Penalizing long delays. SIAM Journal on Discrete Mathematics,. 19:938-951, 2005.

  • G. Zhang, A 3-approximation algorithm for two-dimensional bin packing. Operations Research Letters, 33:121-126, 2005.

  • Christian Gunia. On the analysis of the approximation capability of simple evolutionary algorithms on scheduling Problems. In Proc. Genetic and Evolutionary Computation Conference (GECCO'05), ACM Press, 2005.

2004

  • S. Albers and M. Schmidt. On the performance of greedy algorithms in packet buffering. In Proc. 36th ACM Symposium on Theory of Computing (STOC'04), 35-44, 2004.

  • S. Albers. New results on web caching with request reordering. In Proc. 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA04), 84-92, 2004.

  • S. Albers and T. Radzik. Proceedings of the 12th European Symposium on Algorithms. Springer LNCS 3221, 2004.

  • K. Jansen and G. Zhang, Maximizing the number of packed rectangles. In Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT'04), Springer LNCS 3111, 362-371, 2004.

  • D. Ye and G. Zhang, On-line scheduling of parallel jobs. In Proc. 11th Colloquium on Structural Information and Communication Complexity (SIROCCO), Springer LNCS 3104, 279-290, 2004.

2003

  • S. Albers. Online algorithms: A survey. Mathematical Programming, 97:3-26, 2003. Invited to the journal dedicated to the 18th International Symposium on Mathematical Programming (ISMP'03); Article based upon an invited talk.

  • S. Albers and H. Bals. Dynamic TCP acknowledgement: Penalizing long delays. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), 47-55, 2003.

  • S. Albers and R. van Stee. A study of integrated document and connection caching. In Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP'03), Springer LNCS 2719, 653-667, 2003.

  • S. Albers and M. Büttner. Integrated prefetching and caching in single and parallel disk systems. In Proc. 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA'03), 109-117, 2003.

  • S. Albers and M. Büttner. Integrated prefetching and caching with read and write requests. In Proc. 8th International Workshop on Algorithms and Data Structures (WADS03), Springer 2748, 162-173, 2003.

  • S.S. Seiden and R. van Stee: New bounds for multidimensional packing. Algorithmica, 36:261-293, 2003.

  • M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tichy and N. Vakhania. Preemptive scheduling in overloaded systems. Journal of Computer and Systems Sciences, 67:183-197, 2003.

  • S.S. Seiden, R. van Stee and L. Epstein. New bounds for variable-sized online bin packing. SIAM Journal on Computing, 32:455-469, 2003.

  • E. Bach, J. Boyar, L. Epstein, L.M. Favrholdt, T. Jiang, K.S. Larsen, G.-H. Lin and R. van Stee. Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem. Journal on Scheduling, 6:131-147, 2003.

  • L. Epstein and R. van Stee. Lower bounds for on-line single-machine scheduling. Theoretical Computer Science, 299:439-450, 2003.

  • L. Epstein, C. Imreh and R. Stee. More on weighted servers or FIFO is better than LRU. Theoretical Computer Science, 306:305-317, 2003.

  • A. Kesselman, Y. Mansour and Rob van Stee. Improved competitive guarantees for QoS buffering. In Proc. 11th Annual European Symposium on Algorithms (ESA'03), Springer LNCS 2832, 361-372, 2003.

2002

  • S. Albers and B. Schröder. An experimental study of online scheduling algorithms. ACM Journal of Experimental Algorithmics, 7, 2002. Invited to the journal dedicated to WAE00.

  • S. Albers. On generalized connection caching. Theory of Computing Systems, 35:251-267, 2002. Invited to the journal dedicated to SPAA00.

  • S. Albers and M. Karpinski. Randomized splay trees: Theoretical and experimental results. Information Processing Letters, 81:213-221, 2002.

  • S. Albers. On randomized online scheduling. In Proc. 34th ACM Symposium on Theory of Computing (STOC'02), 134-143, 2002.

  • S. Albers, L.M. Favrholdt and O. Giel. On paging with locality of reference. In Proc. 34th ACM Symposium on Theory of Computing (STOC'02), pages 258-267, 2002.

  • L. Epstein and R. van Stee. Minimizing the maximum starting time on-line. In Proc. 10th Annual European Symposium on Algorithms (ESA'02), Springer LNCS 2461, 449-460, 2002.

  • R. van Stee and J.A. La Poutre. Minimizing the total completion time on-line on a single Machine, using restarts. In Proc. 10th Annual European Symposium on Algorithms (ESA'02), Springer LNCS 2461, 872-883, 2002.

  • L. Epstein, S.S. Seiden and R. van Stee. New bounds for variable-sized and resource augmented online bin packing. Proceedings 29th International Colloquium on Automata, Languages and Programming (ICALP'02), Springer LNCS 2380, 306-317, 2002.

  • M. Chrobak, L. Epstein, J. Noga, J. Sgall, R. van Stee, T. Tichy and N. Vakhania. Preemeptive scheduling in overloaded systems. In Proc. 29th International Colloquium on Automata, Languages and Programming (ICALP'02), Springer LNCS 2380, 800-811, 2002.

  • Leah Epstein, C. Imreh and R. van Stee. More on weighted servers or FIFO is better than LRU. In Proc. 27th International Symposium on Mathematical Foundations of Computer Science (MFCS'02), Springer LNCS 2420, 257-268, 2002.

  • Steven S. Seiden and R. van Stee. New bounds for multi-dimensional packing. In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), 486-495, 2002.

2001

  • S. Albers, M. Charikar and M. Mitzenmacher. Delayed information and action in on-line algorithms. Information and Computation, 170:135-152, 2001.

  • S. Albers, K. Kursawe and S. Schuierer. Exploring unknown environments with obstacles. Algorithmica, 32:123-143, 2001.

  • S. Albers and G. Schmidt. Scheduling with unexpected machine breakdowns. Discrete Applied Mathematics, 110:85-99, 2001.

  • S. Albers and C. Witt. Minimizing stall time in single and parallel disk systems using multicommodity network flows. In Proc. 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'01), Springer LNCS 2129, 12-23, 2001.