Publications

2020

A General Framework for Handling Commitment in Online Throughput Maximization L. Chen, F. Eberle, N. Megow, K. Schewior, and C. Stein. Accepted for publication in Mathematical Programming, February 2020.
On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems A. Marchetti-Spaccamela, N. Megow, J. Schlöter, M. Skutella, and L. Stougie. Accepted for publication at IPDPS 2020.
Scheduling on Hybrid Platforms: Improved Approximability Window Vincent Fagnon, Imed Kacem, Giorgio Lucarelli and Bertrand Simon. Accepted for publication at LATIN 2020.
Scheduling on Two Types of Resources: a Survey Olivier Beaumont, Louis-Claude Canon, Lionel Eyraud-Dubois, Giorgio Lucarelli, Loris Marchal, Clément Mommessin, Bertrand Simon and Denis Trystram. Accepted for publication in ACM Computing Surveys 2020.
Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice. Bertrand Simon, Joachim Falk, Nicole Megow and Jürgen Teich. NG-RES Workshop 2020.

2019

On the Complexity of Anchored Rectangle Packing A. Antoniadis, F. Biermeier, A. Cristi, C. Damerius, R. Hoeksma, D. Kaaser, P. Kling, and L. Nölke. ESA 2019.
A General Framework for Handling Commitment in Online Throughput Maximization L. Chen, F. Eberle, N. Megow, K. Schewior, and C. Stein. Proceedings of IPCO 2019, pp. 141-154, 2019.
Scheduling Self-Suspending Tasks: New and Old Results. J. Chen, T. Hahn, R. Hoeksma, N. Megow, and G. von der Brüggen. To appear in: 31st Conference on Real-Time Systems (ECRTS 2019).
On Index Policies for Stochastic Minsum Scheduling F. Eberle, F. Fischer, J. Matuschke, and N. Megow Operations Research Letters, Vol 47(3):213-218, 2019.
Scheduling Maintenance Jobs in Networks F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, N. Megow, A.T. Richter, R. Rischke. Theoretical Computer Science 754: 107-121, 2019. Special issue of STACS (invited).
Limiting the Memory Footprint when Dynamically Scheduling DAGs on Shared-Memory Platforms. Loris Marchal, Bertrand Simon and Frédéric Vivien. JPDC journal 2019.
Online Scheduling of Task Graphs on Heterogeneous Platforms. Louis-Claude Canon, Loris Marchal, Bertrand Simon and Frédéric Vivien. TPDS journal 2019.
Network Congestion Games are Robust to Variable Demand J. Correa, R. Hoeksma, and M. Schröder. Transportation Research Part B: Methodological, Vol 119:69—78, Jan 2019.
A PTAS for Euclidean TSP with Hyperplane Neighborhoods. A. Antoniadis, K. Fleszar, R. Hoeksma, and K. Schewior. Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).

2018

SUPERSET: A (super)natural variant of the card game SET F. Botler, A. Cristi, R. Hoeksma, K. Schewior, and A. Tönnis. 9th International Conference on Fun with Algorithms (FUN 2018).
Scheduling with Explorable Uncertainty C. Dürr, T. Erlebach, J. Meißner, N. Megow ITCS 2018, 30:1-30:14, 2018.
An O(log m)-Competitive Algorithm for Online Machine Minimization L. Chen, N. Megow and K. Schewior SIAM Journal on Computing 47(6), 2057–2077, 2018.
Dual techniques for scheduling on a machine with varying speed N. Megow, J. Verschae SIAM Journal on Discrete Mathematics 32(3): 1541-1571, 2018.
Online Scheduling of Sequential Task Graphs on Hybrid Platforms. Louis-Claude Canon, Loris Marchal, Bertrand Simon and Frédéric Vivien. Euro-Par Conference, 2018.
Parallel Scheduling of DAGs under Memory Constraints. Loris Marchal, Hanna Nagy, Bertrand Simon and Frédéric Vivien. IPDPS Symposium, 2018.
Malleable Task-graph Scheduling with a Practical Speed-up Model. Loris Marchal, Bertrand Simon, Oliver Sinnen and Frédéric Vivien. TPDS journal 2018.
The price of anarchy for utilitarian scheduling games on related machines. R. Hoeksma and M. Uetz. Discrete Optimization (2018), DOI: 10.1016/j.disopt.2018.08.001.
Approximation Algorithms for Connected Graph Factors of Minimum Weight. K. Cornelissen, R. Hoeksma, B. Manthey, N.S. Narayanaswamy, C.S. Rahul, and M. Waanders. Theory of Computing Systems, 62(2):441—464, 2018.

2017

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments J. Meißner, n. Megow and J. Focke SEA 2017, LIPIcs, No. 22; pp. 22:1–22:14, 2017.
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty J. Meißner, N. Megow and M. Skutella SIAM Journal on Computing 46(4): 1217-1240, 2017.
Packing a Knapsack of Unknown Capacity Y. Disser, M. Klimm, N. Megow, S. Stiller SIAM Journal on Discrete Mathematics 31(3): 1477-1497, 2017.
Scheduling Maintenance Jobs in Networks F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, N. Megow, A.T. Richter, R. Rischke CIAC 2017, LNCS 10236, pp. 19–30, 2017.
Network Congestion Games are Robust to Variable Demand J. Correa, R. Hoeksma, and M. Schröder. Presented at: The 13th Conference on Web and Internet Economics (WINE 2017). Conference proceedings only contained and extended abstract.
Posted price mechanisms for a random stream of customers. J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld. The 2017 ACM conference on Economics and Computation (EC ’17).
A QPTAS for the general scheduling problem with identical release dates. A. Antoniadis, R. Hoeksma, J. Meissner, J. Verschae, and A. Wiese. The 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017).

2016

The Power of Migration in Online Machine Minimization L. Chen, N. Megow and K. Schewior SPAA 2016, pp. 175-184, 2016.
An O(log m)-Competitive Algorithm for Online Machine Minimization L. Chen, N. Megow and K. Schewior SODA 2016, pp. 155-163, 2016.
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio E. Lübbecke, O. Maurer, N. Megow and A. Wiese ACM Transactions on Algorithms 13(1), pp. 15:1-15:34, 2016.
The Power of Recourse for Online MST and TSP N. Megow, M. Skutella, J. Verschae and A. Wiese SIAM Journal on Computing. 45-3, pp. 859-880, 2016.

Copyright notice

    The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.