Publikationen
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), Tórshavn, Faroe Islands, LIPIcs 162, 2020.
- 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.