Publications Working Group Prof. Albers

2008

• Tobias Jacobs
  An Experimental Study of Recent Hotlink Assignment Algorithms
  2008 Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), San Francisco, California, USA Proceedings of the ALENEX, pages: 142 - 151
• Christian Gunia
  Energy-efficient windows scheduling
  2008 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia Proceedings of the SOFSEM 2008: Theory and Practice of Computer Science, Villiam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, Mária Bieliková, volume: Springer LNCS, issue: 4910
• Susanne Albers, Sonja Lauer
  On List Update with Locality of Reference
  2008 Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP '08), volume: LNCS 5125, pages: 96 - 107
• Tobias Jacobs
  On the complexity of optimal hotlink assignment.
  2008 Proc. 15th Annual European Symposium on Algorithms (ESA),, volume: LNCS 5193, pages: 540 - 552
• Susanne Albers
  On the value of coordination in network design
  2008 19th ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, USA Proceedings of the SODA

2007

• Susanne Albers, Rob van Stee
  A study of integrated document and connection caching in the WWW
  2007 Algorithmica, volume: 47, pages: 239 - 252
• Susanne Albers, Tobias Jacobs
  An experimental study of new and known online packet buffering algorithms
  2007 15th Annual European Symposium on Algorithms (ESA), Eilat, Israel Proceedings of the 15th Annual European Symposium on Algorithms (ESA), Lars Arge, Michael Hoffmann, Emo Welzl, volume: Springer LNCS, issue: 4698, pages: 754 - 765
• Tobias Jacobs
  Constant factor approximations for the hotlink assignment problem
  2007 10th International Workshop on Algorithms and Data Structures (WADS) 2007, Halifax, Canada Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS), Frank Dehne, Jörg-Rüdiger Sack, Norbert Zeh, volume: Springer LNCS, issue: 4619, pages: 188 - 200
• Sven O. Krumke, Peter Merz, Tim Nonner, Katharina Rupp
  Distributed approximation algorithms for finding 2-edge-connected subgraphs
  2007 11th International Conference on Principles of Distributed Systems, OPODIS 2007, Guadeloupe Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS), Eduardo Tovar, Philippas Tsigas, Hacène Fouchal, volume: Springer LNCS, issue: 4878, pages: 159 - 173
• Susanne Albers, Hiroshi Fujiwara
  Energy-efficient algorithms for flow time minimization
  2007 Transactions on Algorithms, volume: 3, issue: 4
• Christian Gunia
  Minimal range assignment for broadcasts
  In: Algorithms for Sensor and Ad Hoc Networks
  2007, Springer, Dorothea Wagner, Roger Wattenhofer, pages: 215 - 236, Dorothea Wagner, Roger Wattenhofer, ISBN: 978-3-540-74990-5
• Susanne Albers, Fabian Müller, Swen Schmelzer
  Speed scaling on parallel processors
  2007 19th Symposium on Parallelism in Algorithms and Architecture (SPAA07), San Diego, CA, USA Proceedings of the 19th ACM Symposium on Parallelism in Algorithms and Architecture (SPAA07)
• Martin Hoefer, Alexander Souza
  Tradeoffs and average-case equilibria in selfish routing
  2007 15th Annual European Symposium on Algorithms (ESA), Eilat, Israel Proceedings of the 15th Annual European Symposium on Algorithms (ESA), Lars Arge, Michael Hoffmann, Emo Welzl, volume: Springer LNCS, issue: 4698, pages: 63 - 74

2006

• Susanne Albers, Hiroshi Fujiwara
  Energy-efficient algorithms for flow time minimization
  2006 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS '06) Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, Bruno Durand, Wolfgang Thomas, volume: 3884, pages: 621 - 633
• Patrick Briest, Christian Gunia
  Energy-efficient broadcast scheduling for speed-controlled transmission channels.
  2006 Proc. 7th International Symposium on Algorithms and Computation (ISAAC'06), Springer, volume: LNCS 4288, pages: 670 - 679
• Alexander Souza, Konstantinos Panagiotou
  On Adequate Performance Measures for Paging
  2006 38th Annual Symposium on Theory of Computing (STOC '06), Seattle, USA Proceedings of the 38th Annual Symposium on Theory of Computing, ACM Press, New York, pages: 487 - 496
• Christian Gunia
  On Broadcast Scheduling With Limited Energy
  2006 Conference on Algorithms and Complexity (CIAC '06), Rome Proceedings of the 6th Conference on Algorithms and Complexity, Calamoneri T, Finocchi I, Italiano G, volume: 3998, pages: 151 - 162
• Susanne Albers, Stefan Eilts, Eyal Even-Dar, Yishay Mansour, Liam Roditty
  On Nash equilibria for a network creation game
  2006 17th ACM-SIAM Symposium on Disrecte Algorithms (SODA '06) Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, acm press, New York and siam, Philadelphia, volume: PR 122, pages: 89 - 98
• Susanne Albers
  Online algorithms
  In: Interactive Computation The New Paradigm
  2006, Springer-Verlag, Goldin D.Q., Smolka S.A., Wegner P., pages: 143 - 164, Goldin D.Q., Smolka S.A., Wegner P., ISBN: ISBN: 978-3-540-34666-1

2005

• Guochuan Zhang
  A 3-approximation algorithm for two-dimensional bin packing.
  2005 Operations Research Letters, volume: 33, pages: 121 - 126
• Susanne Albers, Helge Bals
  Dynamic TCP ackowledgment: penalizing long delays
  2005 Siam J Discrete Math, volume: 19, issue: 4, pages: 938 - 951
• Markus Büttner
  Enhanced Prefetching and Caching Strategies for Single and Multi-Disk Systems.
  2005 Acta Informatica, volume: 42, issue: 1, pages: 21 - 42
• Susanne Albers, Markus Büttner
  Integrated prefetching and caching in single and parallel disk systems
  2005 Information and Computation, volume: 198, issue: 1, pages: 24 - 39
• Susanne Albers, Lene M. Favrholdt, Oliver Giel
  On paging with locality of reference
  2005 Journal for Computer and System Sciences, volume: 70, issue: 2, pages: 145 - 175
• Christian Gunia
  On the Analysis of the Approximation Capability of Simple Evolutionary Algorithms on Scheduling Problems
  2005 Genetic and Evolutionary Computation Conference (GECCO '05), Washington D.C., 2005 Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '05), pages: 571 - 578
• Susanne Albers, Markus Schmidt
  On the performance of greedy algorithms in packet buffering
  2005 SIAM Journal on Computing, volume: 35, issue: 2, pages: 278 - 304
• Donglei Du, Xiaoyue Jiang, Guochuan Zhang
  Optimal preemptive online scheduling to minimize 1_p norm on two processors.
  2005 Journal of Industrial and Management Optimization, volume: 1, pages: 345 - 351
• Markus Schmidt
  Packet Buffering: Ranomization Beats Deterministic Algorithms
  2005 22nd Annual Symposium on Theoretical Aspects in Computer Science (STACS 2005) Proceedings of the 22nd Annual Symposium on Theoretical Computer Science, Volker Diekert, Bruno Durand, volume: 3404, pages: 293 - 304
• Markus Büttner, Jussi Rintanen
  Satisfiability Planning with Constraints on the Number of Actions.
  2005 International Conference on Artificial Planning and Scheduling (ICAPS '05) Proceedings of the International Conference on Artificial Planning and Scheduling, pages: 292 - 299

2004

• Klaus Jansen, Guochuan Zhang
  Maximizing the number of packed rectangles
  2004 9th Scandinavian Workshop on Algorithm Theory (SWAT'04) Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), volume: 3111, pages: 362 - 371
• Susanne Albers
  New results on web caching with request reordering
  2004 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA04) Proceedings of the 16th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA04), acm press, New York, pages: 84 - 92
• Susanne Albers, Markus Schmidt
  On the performance of greedy algorithms in packet buffering
  2004 36th Symposium on Theory of Computing (STOC04) Proceedings of the 36th Symposium on Theory of Computing (STOC04), acm press New York, pages: 35 - 44
• Deshi Ye, Guochuang Zhang
  On-line scheduling of parallel jobs
  2004 11th Colloquium on Structural Information and Communication Complexity (SIROCCO) Proceedings of the 11th Colloquium on Structural Information and Communication Complexity (SIROCCO), volume: 3104, pages: 279 - 290
• Susanne Albers (Hrsg.), Tomasz Radzik (Hrsg.)
  Proceedings of the 12th European Symosium on Algorithms
  2004 Springer, page: 838

2003

• Susanne Albers, Rob van Stee
  A study of integrated document and connection caching
  2003 30th International Colloquium on Automata, Languages and Programming (ICALP03) Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP03), volume: 2719, pages: 653 - 667
• Susanne Albers, Helge Bals
  Dynamic TCP acknowledgement: Penalizing long delays
  2003 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA03) Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA03), acm Press, New York and SIAM, Philadelphia, volume: PR 110, pages: 47 - 55
• Alex Kesselman, Yishay Mansour, Rob van Stee
  Improved competitive guarantees for QoS buffering
  2003 11th Annual European Symposium (ESA) Proceedings of the 11th Annual European Symposium (ESA), volume: 2832, pages: 361 - 373
• Susanne Albers, Markus Büttner
  Integrated prefetching and caching in single and parallel disk systems.
  2003 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA03) Proceedings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA03), acm press, New York, pages: 109 - 117
• Susanne Albers, Markus Büttner
  Integrated prefetching and caching with read and write requests
  2003 8th International Workshop on Algorithms and Data Structures (WADS03) Proceedings of the 8th International Workshop on Algorithms and Data Structures (WADS03), volume: 2748, pages: 162 - 173
• Leah Epstein, Rob van Stee
  Lower bounds for on-line single-machine scheduling
  2003 Theoretical Computer Science, volume: 299, issue: 1-3, pages: 439 - 450
• Leah Epstein, Casanad Imreh, Rob van Stee
  More on weighted servers or FIFO is better an LRU
  2003 Theoretical Computer Science, volume: 306, issue: 1-3, pages: 305 - 317
• Steven S. Seiden, Rob van Stee
  New bounds for multi-dimensional packing
  2003 Algorithmica, volume: 36, issue: 3, pages: 261 - 293
• Steven S. Seiden, Rob van Stee, Leah Epstein
  New bounds for variable-sized online bin packing
  2003 SIAM Journal on Computing, volume: 32, issue: 2, pages: 455 - 469
• Susanne Albers
  Online algorithms: A survey
  2003 Mathematical Programming, volume: 97, pages: 3 - 26
• Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomas Tichy, Nodari Vakhania
  Preemptive scheduling in overloaded systems
  2003 Journal fo Computer and Systems Sciences, volume: 67, issue: 1, pages: 183 - 197
• Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favhroldt, Tao Jiang, Kim S. Larsen, Guo-Hui Lin, Rob van Stee
  Tight bounds on the competitive ratio on accomodating sequences for the seat reservation problem
  2003 Journal of Scheduling, volume: 6, issue: 2, pages: 131 - 147

2002

• Susanne Albers, Bianca Schröder
  An experimental study of online scheduling algorithms
  2002 ACM Journal of Experimental Algorithmics, volume: 7
• Leah Epstein, Rob van Stee
  Minimizing the maximum starting time on-line.
  2002 10th European Symposium on Algorithms (ESA) Proceeding the 10th European Symposium on Algorithms (ESA), Möhring R, Raman R, volume: 2461, pages: 449 - 460
• Rob van Stee, Han La Poutré
  Minimizing the total completion time on a single on-line machine, using restarts.
  2002 10th European Symposium on Algorithms Proceedings of the 10th European Symposium on Algorithms (ESA), Möhring R, Raman R, volume: 2461, pages: 872 - 883
• Leah Epstein, Csanad Imreh, Rob van Stee
  More on weighted servers or fifo is better than lru.
  2002 27th Symposium on Mathematical Foundations of Computer Science (MFCS) Proceedings of th 27th Symposium on Mathematical Foundations of Computer Science (MFCS), Diks K, Rytter W, volume: 2420, pages: 257 - 268
• Steven S. Seiden, Rob van Stee
  New bounds for multi-dimensional packing.
  2002 13th Symposium on Discrete Algorithms (SODA) Proceedings of the 13th Symposium on Discrete Algorithms (SODA), acm, New York, siam, Philadelphia, pages: 486 - 495
• Susanne Albers
  On generalized connection caching
  2002 Theory of Computing Systems, volume: 35, issue: 3, pages: 251 - 267
• Susanne Albers, Lene M. Favrholdt, Oliver Giel
  On paging with locality reference
  2002 ACM Symposium on Theory of Computing (STOC02) Proceedings of the 34th ACM Symposium on Theory of Computing (STOC02), acm Press, New York, pages: 258 - 267
• Susanne Albers
  On randomized online scheduling
  2002 ACM Symposium on Theory of Computing (STOC02) Proceedings of the 34th ACM Symposium on Theory of Computing (STOC02), acm Press, New York, pages: 134 - 143
• Marek Chrobak, Leah Epstein, John Noga, Jiri Sgall, Rob van Stee, Tomas Tichy, Nodari Vakhania
  Preemptive scheduling in overloaded systems.
  2002 29th International Colloquium on Automata, Languages, and Programming (ICALP) Proceedings of the 29th International Colloquim on Automata, Languages, and Programming (ICALP), Widmayer P, Triguero F, Morales R, Hennessy M, Eidenbenz S, Conejo R, volume: 2380, pages: 800 - 811
• Susanne Albers, Marek Karpinski
  Randomized splay trees: Theoretic and experimental results
  2002 Information Processing Letters, volume: 81, issue: 4, pages: 213 - 221

2001

• Susanne Albers, Moses Charikar, Michael Mitzenmacher
  Delayed information and action in on-line algorithms
  2001 Information and Computation, volume: 170, issue: 2, pages: 135 - 152
• Susanne Albers, Klaus Kursawe, Sven Schuierer
  Exploring unknown environments with obstacles
  2001 Algorithmica, volume: 32, pages: 123 - 143
• Susanne Albers, Carsten Witt
  Minimizing stall time in single and parallel disk systems using multicommidity network flows
  2001 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), Berkeley, CA, USA Lect Notes Comput Sc, Michel X. Goemans, Klaus Jansen, Jose D. P. Rolim, Luca Trevisan, volume: 2129, pages: 12 - 23
• Susanne Albers, Günter Schmidt
  Scheduling with unexpected machine breakdowns
  2001 Discrete Appl Math, volume: 110, issue: 2-3, pages: 85 - 99

2000

• Susanne Albers, Bianca Schröder
  An experimental study of online scheduling algorithms
  2000 4th Workshop on Algorithm Engineering (WAE00), Saarbrücken Lect Notes Comput Sc, Springer Heidelberg, volume: 1982
• Susanne Albers, Michael Mitzenmacher
  Average case analyes of First-Fit and Random-Fit bin packing
  2000 Random Struct Algor, volume: 16, issue: 3, pages: 240 - 259
• Susanne Albers, Monika R. Henzinger
  Exploring unknown environments
  2000 Siam J Comput, volume: 29, issue: 4, pages: 1164 - 1188
• Susanne Albers
  Generalized connection caching
  2000 12th ACM Symposium on Parallel Algorithms and Architectures (SPAA00), Bar Habor, Maine, USA Proceedings of the 12th ACM Symposium on Parallel Algorithms and Architectures, pages: 70 - 78
• Susanne Albers, Naveen Garg, Stefano Leonardi
  Minimizing stall time in single and parallel disk systems
  2000 J Acm, volume: 47, issue: 6, pages: 969 - 986

1999

• Susanne Albers
  Better bounds for online scheduling
  1999 Siam J Comput, volume: 29, issue: 2, pages: 459 - 473
• Susanne Albers, Klaus Kursave, Sven Schuierer
  Exploring unknown environments with obstacles
  1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA99), Baltimore, MD, USA Proceedings of the 10th Annual ACM-SIAM Symposium on Descrete Algorithms, acm press, pages: 842 - 843
• Susanne Albers
  Online algorithms: A study of graph-theoretic concepts
  1999 25th International Workshop on Graph-Theoretic Concepts in Computer Science (WG99), Ascona, Schweiz Lect Notes Comput Sc, Springer Heidelberg, volume: 1665, pages: 10 - 26
• Susanne Albers, Stefano Leonardi
  Online algorithms: Trends and perspectives
  1999 ACM Computing Surveys
• Susanne Albers, Sanjeev Arora, Sanjeev Khanna
  Page replacement for general caching problems
  1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA99), Baltimore, MD, USA Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, acm press, pages: 31 - 40
• Susanne Albers, Günter Schmidt
  Scheduling with unexpected machine breakdowns
  1999 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX99), Berkeley, CA, USA Lect Notes Comput Sc, Springer Heidelberg, volume: 1671, pages: 269 - 280

1998

• Susanne Albers
  A competitive analysis of the list update problem with lookahead
  1998 Theor Comput Sci, volume: 197, issue: 1-2, pages: 95 - 109
• Susanne Albers, Michael Mitzenmacher
  Average case analyses of First-Fit and Random-Fit bin packing
  1998 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA98), San Francisco, CA, USA Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, acm press, pages: 290 - 299
• Susanne Albers, Michael Mitzenmacher
  Average case analyses of list update algorithms, with applications to data compression
  1998 Algorithmica, volume: 21, issue: 3, pages: 312 - 329
• Susanne Albers
  Improved randomized on-line algorithms for the list update problem
  1998 Siam J Comput, volume: 27, issue: 3, pages: 682 - 693
• Susanne Albers, Naveen Garg, Stefano Leonardi
  Minimizing stall time in single and parallel disk systems
  1998 30th Annual ACM Symposium on Theory of Computing (STOC98), Dallas, Texas, USA Proceedings of the 30th Annual Symposium on Theory of Computing, acm press, pages: 454 - 462
• Susanne Albers, Hisashi Koga
  New on-line algorithms for the page replication problem
  1998 J Algorithm, volume: 27, issue: 1, pages: 75 - 96
• Susanne Albers, Moses Charikar, Michael Mitzenmacher
  On delayed information and action in on-line algorithms
  1998 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS98), Palo Alto, CA, USA Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, pages: 71 - 80
• Susanne Albers, Jeffrey Westbrook
  Self-organizing data structures
  In: Online-Algorithms: The State of the Art
  1998, Springer Verlag, A. Fiat, G.J. Woeginger, pages: 13 - 51, A. Fiat, G.J. Woeginger, ISBN: 978-3540649175

1997

• Susanne Albers
  Better bounds for online scheduling
  1997 29th Annual ACM Symposium on Theory of Computing (STOC97), El Paso, Texas, USA Proceedings of the29th Annual ACM Symposium on Theory of Computing, pages: 130 - 139
• Susanne Albers
  Competitive online Algorithms
  Optima, volume: 54, pages: 1 - 8, 1997
• Susanne Albers, Monika R. Henzinger
  Exploring unknown environments
  1997 29th Annual ACM Symposium on Theory of Computing (STOC97), El Paso, Texas, USA Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages: 416 - 425
• Susanne Albers, Torben Hagerup
  Improved parallel integer sorting without concurrent writing
  1997 Inform Comput, volume: 136, issue: 1, pages: 25 - 51
• Susanne Albers
  On the influence of lookahead in competitive paging algorithms
  1997 Algorithmica, volume: 18, issue: 3, pages: 283 - 305
• Susanne Albers, Michael Mitzenmacher
  Revisiting the COUNTER algorithms for list update
  1997 Inform Process Lett, volume: 64, issue: 3, pages: 155 - 160

1996

• Susanne Albers, Michael Mitzenmacher
  Average case analyses of list update algorithms, with applications to data compression
  1996 23rd International Colloquium on Automata, Languages, and Programming (ICALP96), Paderborn Proceedings of the 23rd International Colloquium on Automata, Languages, and Programming, Springer Heidelberg, volume: 1099, pages: 514 - 525
• Susanne Albers
  Lecture notes on competitive online algorithms
  BRICS Lecture Series, volume: 96, issue: 2, 1996

1995

• Susanne Albers, Bernhard von Stengel, Ralph Werchner
  A combinded BIT and TIMESTAMP algorithm for the list update problem
  1995 Inform Process Lett, volume: 56, issue: 3, pages: 135 - 139
• Susanne Albers
  Improved randomized on-line algorithms for the list update problem
  1995 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA95), San Franciso, CA, USA Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages: 412 - 419
• Susanne Albers, Hisashi Koga
  Page migration with limited local memory capacity
  1995 4th International Workshop on Algorithms and Data Structures (WADS95), Kingston, Ontario, Canada Proceedings of the 4th International Workshop on Algorithms and Data Structures, Springer Heidelberg, volume: 955, pages: 147 - 158

1994

• Susanne Albers
  A competitive analysis of the list update problem with lookahead
  1994 19th International Symposium on Mathematical Foundations of Computer Science (MFCS94), Kosice, Slovakia Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science, Springer Heidelberg, volume: 841, pages: 201 - 210
• Susanne Albers, Hisashi Koga
  New on-line algorithms for the page replication problem
  1994 4th Scandinavian Workshop on Algorithm Theory (SWAT94), Aarhus, Dänemark Proceedings of the 4th Scandinavian Workshop on Algorithm Theory, Springer Heidelberg, volume: 824, pages: 25 - 36

1993

• Susanne Albers
  On the influence of lookahead in competitive paging algorithms
  1993 1st Annual European Syposium on Algorithms (ESA93), Bad Honnef Proceedings of the 1st Annual European Symposium on Algorithms, Springer Heidelberg, volume: 726, pages: 1 - 12
• Susanne Albers, Peter Brucker
  The complexity of one-machine batching problems
  1993 Discrete Appl Math, volume: 47, issue: 1, pages: 87 - 107

1992

• Susanne Albers, Torben Hagerup
  Improved parallel integer sorting without concurrent writing
  1992 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA92), Orlando, Florida, USA Proceedings of the 3rd Annual ACM-SIAM Symposium on Dicscrete Algorithms, pages: 463 - 472