Startseite
Publikationen
2025
S. Albers, S. Schubert. Optimal algorithms for online b-matching with variable vertex capacities . Algorithmica 87(2): 167-190, 2025. G. Goranci, M. Henzinger, H. Räcke, A.R. Sricharan. Incremental approximate maximum flow via residual graph sparsification . In Proc. 52nd International Colloquium on Automata, Languages, and Programming, (ICALP25), LIPIcs 334, 91:1-91:20, 2025. S. Albers, S. Schubert. Online b-matching with stochastic rewards . In Proc. 50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM25), Springer LNCS 15538, 37-50, 2025. H. Räcke, S. Schmid, R. Zabrodin. Tight bounds for online balanced partitioning in the generalized learning model . In Proc. 37rd Symposium on Parallelism in Algorithms and Architectures (SPAA25), 240-254, 2025. S. Albers, G.W. van der Heijden. Online busy time scheduling with flexible jobs . In Proc. 18th Annual International Conference on Combinatorial Optimization and Applications (COCOA25), Springer LNCS, 2025. Best Paper Award. M. Henzinger, E. Kosinas, R. Münk, H. Räcke:. Efficient contractions of dynamic graphs - with applications . In Proc. 33rd Annual European Symposium on Algorithms (ESA25), LIPIcs 351, 36:1-4:14, 2025. F. Schumann, G.W. van der Heijden, S. Rinderle-Ma. Instance Configuration and Scheduling Based on the Resource-Augmented Process Structure Tree . In Proc. Business Process Management Forum (BPM25), Springer LBIP 564, 110-127, 2025. S. Albers, W. Gálvez, Ö.B. Özdemir. On the 2d demand bin packing problem: Hardness and approximation algorithms . In Proc. 13th Latin-American Symposium on Algorithms, Graphs and Optimization (LAGOS25), Procedia Computer Science, Elsevier, 301-308, 2025.
2024
H. Räcke, S. Schmid, R. Vintan. Fast algorithms for loop-free network updates using linear programming and local search . In Proc. IEEE International Conference on Computer Communications (INFOCOM24), 1930-1939, 2024. G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan:. Electrical flows for polylogarithmic competitive oblivious routing . In Proc. 15th Conference on Innovations in Theoretical Computer Science Conference (ITCS24), LIPIcs 287, 55:1-55:22, 2024. K. Hanauer, M. Henzinger, R. Münk, H. Räcke, M. Vötsch:. Expander hierarchies for normalized cuts on graphs . In Proc.30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD24), 1016-1027, 2024.
2023
S. Albers, W. Galvez, M. Janke. Machine covering in the random-order model . Algorithmica, 85(6): 1560-1585, 2023. S. Albers, J. Quedenfeld. Algorithms for right-sizing heterogeneous data-centers . ACM Trans. Parallel Comput. 10(4): 20(1)-20(28), 2023. H. Räcke, S. Schmid, R. Zabrodin. Polylog-competitive algorithms for dynamic balanced graph partitioning for ring demands . In Proc. 35th Symposium on Parallelism in Algorithms and Architectures (SPAA23), 403-413, 2023. M. Henzinger, S. Neumann, H. Räcke, S. Schmid. Dynamic maintenance of monotone dynamic programs and applications . In Proc. 40th International Symposium on Theoretical Aspects of Computer Science, (STACS23), LIPIcs 254, 36:1-36:16, 2023.
2022
B. Haeupler, H. Räcke, M. Ghaffari. Hop-constrained expander decompositions, oblivious routing, and distributed universal optimality . In Proc. 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC22), 1325–1338, 2022. S. Albers, S. Schubert. Tight bounds for online matching in bounded-degree graphs with vertex capacities . In Proc. 30th Annual European Symposium on Algorithms (ESA22), LIPIcs 244, 4:1-4:14, 2022. H. Räcke, S. Schmid, R. Zabrodin. Approximate dynamic balanced graph partitioning . In Proc. 34rd Symposium on Parallelism in Algorithms and Architectures (SPAA22), 401-409, 2022. S. Albers, S. Schubert. Online ad allocation in bounded-degree graphs . In Proc. 18th International Conference on Web and Internet Economics (WINE22), Springer LNCS 13778, 60-77, 2022. A. Adamaszek, A. Czumaj, M. Englert, H. Räcke. Almost tight bounds for reordering buffer management . SIAM J. Comput., 51(3): 701-722, 2022. S. Albers, J. Quedenfeld. Optimal algorithms for right-sizing data centers . ACM Trans. Parallel Comput., 9(4): 15:1-15:40, 2022. S. Albers. Energy-efficient scheduling . In Algorithms for Big Data - DFG Priority Program 1736, Springer LNCS 13201, 196-212, 2022.
2021
S. Albers, J. Quedenfeld. Algorithms for right-sizing heterogeneous data centers . In Proc. 33rd Symposium on Parallelism in Algorithms and Architectures (SPAA21), 48-58, 2021. S. Albers, S. Schubert. Optimal algorithms for online b-matching with variable vertex capacities . In Proc. 24rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX21), LIPIcs 207, 2:1-2:18, 2021. M. Henzinger, S. Neumann, H. Räcke, Stefan Schmid. Tight bounds for online graph partitioning . In Proc. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA21), 2799-2818, 2021. W. Gálvez, F. Grandoni, A. Khan, D. Ramírez-Romero, A. Wiese. Improved approximation algorithms for 2-dimensional knapsack: Packing into multiple L-Shapes, spirals, and more . In Proc. 37th International Symposium on Computational Geometry (SoCG21), LIPIcs 189, 39:1-39:17, 2021. S. Albers, M. Janke. Online makespan minimization with budgeted uncertainty . In Proc. 17th International Symposium on Algorithms and Data Structures (WADS21), Springer LNCS 12808, 43-56, 2021. S. Albers, J. Quedenfeld. Algorithms for energy conservation in heterogeneous data centers . In Proc. 12th International Conference on Algorithms and Complexity (CIAC21), Springer LNCS 12701, 75-89, 2021. W. Gálvez, F. Grandoni, A. Jabal Ameli, K. Khodamoradi. Approximation algorithms for demand strip packing . In Proc. 24rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX21), LIPIcs 207, 20:1-20:25, 2021. S. Albers, A. Eckl. Scheduling with testing on multiple identical parallel machines . In Proc. 17th International Symposium on Algorithms and Data Structures (WADS21), Springer LNCS 12808, 29-42, 2021. G. Goranci, H. Räcke, T. Saranurak, Z. Tan. The expander hierarchy and its applications to dynamic graph algorithms . In Proc. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA21), 2212-2228, 2021. S. Albers, M. Janke. Scheduling in the secretary model . In Proc. 41st Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS21), LIPIcs, 2021. S. Albers, W. Gálvez, M. Janke. Machine covering in the random-order model . In Proc. 32nd International Symposium on Algorithms and Computation (ISAAC21), LIPIcs, 2021. T. Forner, H. Räcke, S. Schmid. Online balanced repartitioning of dynamic communication patterns in polynomial time . In Proc. 2nd Symposium on Algorithmic Principles of Computer Systems (APOCS21), 40-54, 2021. R. Münk, M. Rost, H. Räcke, S. Schmid. It's good to relax: Fast profit approximation for virtual networks with latency constraints . In Proc. 20th Annual IFIP Networking Conference, 1-3, 2021. S. Albers, D. Kraft. On the value of penalties in time-inconsistent planning . ACM Trans. Economics and Comput., 9(3): 17:1-17:18, 2021. S. Albers, M. Janke. Scheduling in the random-order model . Algorithmica, 83(9): 2803-2832, 2021. S. Albers, A. Khan, L. Ladewig. Best Fit bin packing with random order revisited . Algorithmica, 83(9): 2833-2858, 2021. S. Albers, A. Khan, L. Ladewig. Improved online algorithms for knapsack and GAP in the random order model . Algorithmica, 83(6): 1750-1785, 2021. W. Gálvez, F. Grandoni, A. Jabal Ameli, K. Sornat. On the cycle augmentation problem: Hardness and approximation algorithms . Theory Comput. Syst., 65(6): 985-1008, 2021. S. Albers, L. Ladewig. New results for the k-secretary problem . Theor. Comput. Sci., 863: 102-119, 2021. S. Albers, S. Schraink. Tight bounds for online coloring of basic graph classes . Algorithmica, 83(1): 337–360, 2021.
2020
S. Albers, M. Janke. Scheduling in the random-order model . In Proc. 47th International Colloquium on Automata, Languages, and Programming, (ICALP20), LIPIcs 168, 68:1-68:18, 2020. P. Czerner, H. Räcke. Compact oblivious routing in weighted graphs . In Proc. 28th Annual European Symposium on Algorithms (ESA20), LIPIcs 173, 36:1-36:23, 2020. S. Albers. Editor of the Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT20) S. Albers, M. Janke. New bounds for randomized list update in the paid exchange model . In Proc. 37th International Symposium on Theoretical Aspects of Computer Science, (STACS20), LIPIcs 154, 12:1-12:17, 2020. S. Albers, A. Khan, L. Ladewig. Best Fit bin packing with random order revisited . In Proc. 45th International Symposium on Mathematical Foundations of Computer Science (MFCS20), LIPIcs 170, 7:1-7:15, 2020. S. Albers, A. Eckl. Explorable uncertainty in scheduling with non-uniform testing times . In Proc. 18th Workshop on Approximation and Online Algorithms, (WAOA20), Springer LNCS 12806, 127-142, 2020. W. Gálvez, F. Grandoni, A. Jabal Ameli, K. Jansen, A. Khan, M. Rau. A tight (3/2+ε) approximation for skewed strip packing . In Proc. 23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX20), LIPIcs 176, 44:1-44:18, 2020. W. Gálvez, J.A. Soto, J. Verschae. Symmetry exploitation for online machine covering with bounded migration . ACM Transactions on Algorithms, 16(4), 43:1-43:22, 2020.
2019
S. Albers, L. Ladewig. New results for the k-secretary problem . In Proc. 30th International Symposium on Algorithms and Computation (ISAAC19), LIPIcs 149, 18:1-18:19, 2019. S. Albers, A. Khan, L. Ladewig. Improved online algorithms for knapsack and GAP in the random order model . In Proc. 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX19), LIPIcs 145, 22:1-22:23, 2019. A. Birx, Y. Disser, K. Schewior. Improved bounds for open online dial-a-ride on the line . In Proc. 22nd International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX19), LIPIcs 145, 21:1-21:22, 2019. S. Albers. On energy conservation in data centers . ACM Trans. Parallel Comput., 6(3): 13:1-13:26, 2019. H. Räcke, S. Schmid. Compact oblivious routing . In Proc. 27th Annual European Symposium on Algorithms (ESA19), LIPIcs 144, 75:1-75:14, 2019. E. Bampis, B. Escoffier, K. Schewior, A. Teiller. Online multistage subset maximization problems . In Proc. 27th Annual European Symposium on Algorithms (ESA19), LIPIcs 144, 11:1-11:14, 2019. L. Chen, F. Eberle, N. Megow, K. Schewior, C. Stein. A general framework for handling commitment in online throughput maximization . In Proc. 20th International Conference on Integer Programming and Combinatorial Optimization (IPCO19), Springer LNCS 11480, 141-154, 2019. J.R. Correa, P. Dütting, F.A. Fischer, K. Schewior. Prophet inequalities for i.i.d. random variables from an unknown distribution . In Proc. 20th ACM Conference on Economics and Computation (EC19), 3-17, 2019. A. Adamaszek, A. Czumaj, M. Englert, H. Räcke. An O(log k)-competitive algorithm for generalized caching . ACM Trans. Algorithms, 15(1):6:1-6:18, 2019. S. Albers, D. Kraft. Motivating time-inconsistent agents: A computational approach . Theory of Computing Systems, 63(3):466–487, 2019. A. Antoniadis, K. Fleszar, R. Hoeksma, K. Schewior. A PTAS for Euclidean TSP with hyperplane neighborhoods . In Proc. 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA19), 1089-1105, 2019. S. Albers, A. Passen. New online algorithms for story scheduling in web advertising . Algorithmica, 81(1):1-25, 2019. A. Sidiropoulos, M. Badoiu, K. Dhamdhere, A. Gupta, P. Indyk, Y. Rabinovich, H. Räcke, R. Ravi. Approximation algorithms for low-distortion embeddings into low-dimensional spaces . SIAM J. Discrete Math., 33(1):454-473, 2019. M. Englert, H. Räcke, R. Stotz. Polylogarithmic Guarantees for Generalized Reordering Buffer Management . In Proc. 60th Annual Symposium on Foundations of Computer Science, (FOCS), 38-59, 2019.
2018
S. Albers, D. Frascaria. Quantifying competitiveness in paging with locality of reference . Algorithmica, 80(12):3563-3596, 2018. N. Olver, K. Pruhs, K. Schewior, R. Sitters, L. Stougie. The itinerant list update problem . In Proc. 16th International Workshop on Approximation and Online Algorithms (WAOA18), 310-326, 2018. H. Räcke, R. Schwartz, R. Stotz. Trees for vertex cuts, hypergraph cuts and minimum hypergraph bisection . In Proc. 30th Symposium on Parallelism in Algorithms and Architectures (SPAA18), 23-32, 2018. F. Botler, A. Cristi, R. Hoeksma, K. Schewior, A. Tönnis. SUPERSET: A (super)natural variant of the card game SET . In Proc. 9th International Conference on Fun with Algorithms (FUN18), 12:1-12:17, 2018. S. Albers, J. Quedenfeld. Optimal algorithms for right-sizing data centers . In Proc. 30th Symposium on Parallelism in Algorithms and Architectures (SPAA18), 363-372, 2018.
2017
S. Albers, E. Bampis, D. Letsios, G. Lucarelli, R. Stotz. Scheduling on power-heterogeneous processors . Information and Computation, 257:22-33, 2017. S. Albers, D. Kraft. The price of uncertainty in present-biased planning . In Proc. 13th International Conference on Web and Internet Economics (WINE17), Springer LNCS, 2017. S. Albers, M. Hellwig. On the value of job migration in online makespan minimization . Algorithmica, 79(2):598-623, 2017. S. Albers, S. Schraink. Tight bounds for online coloring of basic graph classes . In Proc. 25th Annual European Symposium on Algorithms (ESA17), 7:1-7:14, 2017. S. Albers, D. Kraft. On the value of penalties in time-inconsistent planning . In Proc. 44rd International Colloquium on Automata, Languages, and Programming (ICALP17), 10:1-10:12, 2017. M. Kohler, H. Räcke. Reordering buffer management with a logarithmic guarantee in general metric spaces . In Proc. 44rd International Colloquium on Automata, Languages, and Programming (ICALP17), 33:1-33:12, 2017. Y. Giannakopoulos, E. Koutsoupias, P. Lazos. Online market intermediation . In Proc. 44rd International Colloquium on Automata, Languages, and Programming (ICALP17), 47:1-47:14, 2017. S. Albers. On energy conservation in data centers . In Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA17), 35-44, 2017. K. Jansen, K.-M. Klein, M. Kosche, L. Ladewig. Online strip packing with polynomial migration . In Proc. 20th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX17), 13:1-13:1, 2017. J. Quedenfeld, S. Rahmann. Analysis of min-hashing for variant tolerant DNA read mapping . In Proc. 17th International Workshop on Algorithms in Bioinformatics (WABI17), 21:1-21:13, 2017. S. Albers, M. Hellwig. Online makespan minimization with parallel schedules . Algorithmica, 78(2):492-520, 2017. S. Albers, M. Bichler, F. Brandt, P. Gritzmann, R. Kolisch. Algorithmic Economics und Operations Research . Informatik Spektrum, Sonderheft 50 Jahre Informatik München, 42(2):165-171, 2017. M. Englert, Harald Räcke. Reordering buffers with logarithmic diameter dependency for trees . In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA17), 1224-1234, 2017.
2016
S. Albers, D. Kraft. Motivating time-inconsistent agents: A computational approach . In Proc. 12th International Conference on Web and Internet Economics (WINE16), Springer LNCS 10123, 309-323, 2016. Y. Giannakopoulos, E. Koutsoupias, M. Kyropoulou. The anarchy of scheduling without money . In Proc. 9th International Symposium on Algorithmic Game Theory, (SAGT16), Springer LNCS 9928, 302-314, 2016. G. Goranci, Harald Räcke. Vertex sparsification in trees . In Proc. 14th International Workshop on Approximation and Online Algorithms (WAOA16), Springer LNCS 10138, 103-115, 2016. S. Albers, S. Lauer. On list update with locality of reference . J. Comput. Syst. Sci., 82(5):627-653, 2016. S. Dehghani, S. Ehsani, M. Hajiaghayi, V. Liaghat, H. Räcke, S. Seddighin. Online weighted degree-bounded Steiner networks via novel online mixed packing/covering . In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP16), 42:1-42:14, 2016. F. Schalekamp, A. van Zuylen, S. van der Ster. A duality based 2-approximation algorithm for maximum agreement forest . In Proc. 43rd International Colloquium on Automata, Languages, and Programming (ICALP16), 70:1-70:14, 2016. S. Albers, E. Bampis, D. Letsios, G. Lucarelli, R. Stotz. Scheduling on power-heterogeneous processors . In Proc. 12th Latin American Symposium on Theoretical Informatics (LATIN16), Springer LNCS 9644, 41-54, 2016. H. Räcke, R. Stotz. Improved Approximation Algorithms for balanced partitioning problems . In Proc. 33rd Symposium on Theoretical Aspects of Computer Science (STACS16), 58:1-14, 2016.
2015
S. Albers, A. Antoniadis, G. Greiner. On multi-processor speed scaling with migration . J. Comput. Syst. Sci., 81(7):1194-1209, 2015. S. Albers, D. Frascaria. Quantifying competitiveness in paging with locality of reference . In Proc. 42nd International Colloquium on Automata, Languages, and Programming (ICALP15), Springer LNCS 9134, 26-38, 2015. S. Albers. Modeling Real-World Data Sets (Invited Talk) . Symposium on Computational Geometry, 872-872, 2015. E. Bampis, D. Letsios, G. Lucarelli. Green scheduling, flows and matchings . Theor. Comput. Sci., 579:126-136, 2015.
2014
D. Kraft, S. Fadaei, M. Bichler. Fast convex decomposition for truthful social welfare approximation . In Proc. 10th International Conference on Web and Internet Economics (WINE14), Springer LNCS 8877, 120-132, 2014. S. Albers, S. Eilts, E. Even-Dar, Y. Mansour, L. Roditty. On Nash equilibria for a network creation game . ACM Trans. Economics and Comput., 2(1):2, 2014. S. Albers, F. Müller, S. Schmelzer. Speed Scaling on Parallel Processors . Algorithmica, 68(2):404-425, 2014. S. Albers, A. Antoniadis. Race to idle: New algorithms for speed scaling with a sleep state . ACM Transactions on Algorithms, 10(2):9, 2014. S. Albers, M. Hellwig. Online makespan minimization with parallel schedules . In Proc. 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT14), Springer LNCS 8513, 13-25, 2014. E. Bampis, D. Letsios, G. Lucarelli. Speed-scaling with no preemptions . In Proc. 25th International Symposium on Algorithms and Computation (ISAAC'14) , Springer LNCS 8889, 259-269, 2014. E. Bampis, V. Chau, D. Letsios, G. Lucarelli, I. Milis, G. Zois. Energy efficient scheduling of MapReduce jobs . In Proc. 20th International Conference on Parallel Processing (EUROPAR'14), Springer LNCS 8632, 198-209, 2014. E. Bampis, D. Letsios, G. Lucarelli. A note on multiprocessor speed scaling with precedence constraints . In Proc. 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA14), 138-142, 2014.
2013
S. Albers, P. Lenzner. On approximate Nash equilibria in network design . Internet Mathematics, 9(4):384-405, 2013. S. Albers, A. Passen. New online algorithms for story scheduling in web advertising . In Proc. 40th International Colloquium on Automata, Languages, and Programming (ICALP13), Springer LNCS 7966, 46-458, 2013. S. Albers. Recent advances for a classical scheduling problem . In Proc. 40th International Colloquium on Automata, Languages, and Programming (ICALP13), Springer LNCS 7966, 4-14, 2013. Susanne Albers. Recent Results for Online Makespan Minimization (Invited Talk) . In Proc. 19th International Conference on Computing and Combinatorics (COCOON13), Springer LNCS 7936, 1-3, 2013.
