Publikationen
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.
- 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.