Menu

• Team
  • Prof. Dr. Nicole Megow
  • Dr. Syamantak Das
  • Dr. Ruben Hoeksma
  • Franziska Eberle
  • Lukas Nölke
• Teaching
• Projects
• Research Seminar
• Offers

Refereed conference publications

• On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems (with Marchetti-Spaccamela, J. Schlöter, M. Skutella and L. Stougie)
  Proc. of IPDPS 2020.
• A general framework for handling commitment in online throughput maximization (with L. Chen, F. Eberle, K. Schewior, C. Stein)
  Proc. of 20th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 141-154, 2019. [pdf] , arxiv
• Scheduling Self-Suspending Tasks: New and Old Results (with J.J. Chen, R. Hoeksma, T. Hahn and G. von der Brueggen)
  Proc. of 31st Euromicro Conference on Real-Time Systems (ECRTS), LIPIcs 16:1--16:23, 2019. [pdf]
• Scheduling with Explorable Uncertainty (with C. Dürr, T. Erlebach, J. Meißner)
  In Proc. of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 30:1-30:14, 2018. [pdf]
• Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments (with J. Meißner and J. Focke)
  In Proc. of the 16th International Symposium on Experimental Algorithms (SEA 2017), LIPIcs, Article No. 22; pp. 22:1–22:14, 2017. [pdf]
• Scheduling Maintenance Jobs in Networks (with F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, A.T. Richter, R. Rischke)
  In Proc. of the 10th International Conference on Algorithms and Complexity (CIAC 2017), LNCS 10236, pp. 19–30, 2017. [pdf]
• The Power of Migration in Online Machine Minimization (with L. Chen and K. Schewior)
  In Proc. of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pp. 175-184, 2016. [pdf]
• An O(log m)-Competitive Algorithm for Online Machine Minimization (with L. Chen and K. Schewior)
  In Proc. of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 155-163, 2016. [pdf]
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (with J. Meißner and M. Skutella)
  In Proc. of the 23rd European Symposium on Algorithms (ESA 2015), LNCS 9294, pp. 878-890, Springer, 2015. [pdf]
• Stochastic and Robust Scheduling in the Cloud (with L. Chen, R. Rischke and L. Stougie)
  In Proc. of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015), LIPIcs 40, pp. 175-186, 2015. [pdf]
• Optimal Algorithms and a PTAS for Cost-Aware Scheduling (with L. Chen, R. Rischke, L. Stougie and J. Verschae)
  In Proc. of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), LNCS 9235, pp. 211-222, 2015. [pdf]
• Packing a Knapsack of Unknown Capacity (with Y. Disser, M. Klimm and S. Stiller)
  In Proc. of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2015), pp. 276-287, 2015. [pdf]
• Polynomial-time exact schedulability tests for harmonic real-time tasks (with V. Bonifaci, A Marchetti-Spaccamela and A. Wiese)
  In Proc. of the 34th IEEE Real-Time Systems Symposium (RTSS 2013), pp. 236-245, 2013. [pdf]
• Dual techniques for scheduling on a machine with varying speed (with J. Verschae)
  In Proc. of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), LNCS 7965, pp. 745-756, Springer, 2013. [pdf]
• Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints (with J. Mestre)
  In Proc. of the 4th Conference on Innovations in Theoretical Computer Science (ITCS 2013), pp. 495-504, 2013. [pdf]
• A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio (with E. Günther, O. Maurer and A. Wiese)
  In Proc. of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 118-128, 2013. [pdf]
• The Power of Recourse for Online MST and TSP (with M. Skutella, J. Verschae and A. Wiese)
  In Proc. of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS 7391, pages 689-700, Springer, 2012. [pdf]
• Meeting deadlines: How much speed suffices? (with S. Anand and N. Garg)
  In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), LNCS 6755, pages 232-243, Springer, 2011. [pdf]
  Erratum for "Meeting deadlines: How much speed suffices?", 2015. [pdf]
• Online Graph Exploration: New Results on Old and New Algorithms (with K. Mehlhorn and P. Schweitzer)
  In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), LNCS 6756, pages 478-489, Springer, 2011.
• Scheduling real-time mixed-criticality jobs (with S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela and L. Stougie)
  In Proc. of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), LNCS 6281, pages 90-101. Springer, 2010.
• Universal sequencing on a single machine (with L. Epstein, A. Levin, A. Marchetti-Spaccamela, J. Mestre, M. Skutella and L. Stougie)
  In Proc. of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010), LNCS 6080, pages 230-243. Springer, 2010.
• Algorithms and Complexity for Periodic Real-Time Scheduling (V. Bonifaci, H.-L. Chan and A. Marchetti-Spaccamela)
  In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 1350-1359, 2010.
• Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width (with E. Günther and F. König)
  In Proc. of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009), LNCS 5893, pages 170-181. Springer, 2010.
• Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs (with J.R. Correa, R. Raman and K. Suchan)
  In 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009), Paris, France, 2009.
• Coping with incomplete information in scheduling - stochastic and online models
  In Operations Research Proceedings, Springer, pages 17-22, 2008.
  Invited submission for winner of the Dissertation Award of the German Operations Research Society (GOR).
• Approximation in Preemptive Stochastic Online Scheduling (with T. Vredeveld)
  In Proc. of the 14th European Symposium on Algorithms (ESA 2006), LNCS 4168, pages 516-527, 2006.
• The Online Target Date Assignment Problem (S. Heinz, J. Rambau, S.O. Krumke, A. Tuchscherer and T. Vredeveld)
  In Proc. of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), LNCS 3879, pages 230-243, 2006.
• Stochastic Online Scheduling on Parallel Machines (with M. Uetz and T. Vredeveld)
  In Proc. of the 2nd Workshop on Approximation and Online Algorithms (WAOA 2004), LNCS 3351, pages 167-180, 2005.
• How to Whack Moles (with S.O. Krumke and T. Vredeveld)
  In Proc. of the First Workshop on Approximation and Online Algorithms (WAOA 2003), LNCS 2909, pages 192-205, 2004.
• Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line Algorithms (with A.S. Schulz)
  In Proc. of the First Workshop on Approximation and Online Algorithms (WAOA 2003), LNCS 2909, pages 227-234, 2004.

Journal publications

• On Index Policies for Stochastic Minsum Scheduling (with F. Eberle, F. Fischer, J. Matuschke)
  Operations Research Letters Vol 47(3):213-218, 2019. link
• Scheduling Maintenance Jobs in Networks (with F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, A.T. Richter, R. Rischke)
  Theoretical Computer Science 754: 107-121, 2019. Special issue of STACS (invited). [pdf]
• An O(log m)-Competitive Algorithm for Online Machine Minimization (with L. Chen and K. Schewior)
  SIAM Journal on Computing 47(6), 2057–2077, 2018. [pdf]
• Dual techniques for scheduling on a machine with varying speed (with J. Verschae)
  SIAM Journal on Discrete Mathematics 32(3): 1541-1571, 2018. [pdf]
• Randomization Helps Computing a Minimum Spanning Tree under Uncertainty (with J. Meißner and M. Skutella)
  SIAM Journal on Computing 46(4): 1217-1240, 2017. [pdf]
• Packing a Knapsack of Unknown Capacity (with Y. Disser, M. Klimm, S. Stiller)
  SIAM Journal on Discrete Mathematics 31(3): 1477-1497, 2017. [pdf]
• A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio (with 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 (with M. Skutella, J. Verschae and A. Wiese)
  SIAM Journal on Computing. 45-3, pp. 859-880, 2016. [pdf]
• Clique partitioning with value-monotone submodular cost (with J. Correa)
  Discrete Optimization, Vol. 15, pp. 26-36, 2015. [pdf]
• Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width (with E. Günther and F. König)
  Journal of Combinatorial Optimization, Vol. 27, pp. 164-181, 2014. [pdf]
• A Tight 2-Approximation for Preemptive Stochastic Scheduling (with T. Vredeveld)
  Mathematics of Operations Research, Vol. 39, pp. 1297-1310, 2014. [pdf]
• On Eulerian extensions and their application to no-wait flowshop scheduling (with W. Höhn and T. Jacobs)
  Journal of Scheduling, Vol. 15, pp. 295-309, 2012. [pdf]
• Algorithms and Complexity for Periodic Real-Time Scheduling (with V. Bonifaci, H.-L. Chan and A. Marchetti-Spaccamela)
  ACM Transactions on Algorithms, Vol. 9, pp. 601-619, 2012. [pdf]
• Scheduling real-time mixed-criticality jobs (with S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela and Stougie, L.)
  IEEE Transactions on Computers, Vol. 61, pp. 1140-1152, 2012. [pdf] [erratum]
• A note on sorting buffers offline (with H.-L. Chan, R. Sitters and R. van Stee)
  Theoretical Computer Science, Vol. 423, pp. 11-18, 2012. [pdf]
• Universal sequencing on a single unreliable machine (with L. Epstein, A. Levin, J. Mestre, A. Marchetti-Spaccamela, M. Skutella and L Stougie)
  SIAM Journal on Computing, Vol. 41, pp. 565-586, 2012. [pdf]
• Online graph exploration: New results on old and new algorithms (with K. Mehlhorn and P. Schweitzer)
  Theoretical Computer Science, Vol. 463, pp. 62-72, 2012. [pdf]
  Special Issue on Theory and Applications of Graph Searching Problems.
• Decision Support and Optimization in Shutdown and Turnaround Scheduling (with R. Möhring and J. Schulz)
  INFORMS J. on Computing, Vol. 23, pp. 189-204, 2011. [pdf]
• Optimizing the Landside Operation of a Container Terminal (with G. Froyland, T. Koch, E. Duane and H. Wren)
  OR Spectrum, Vol. 30, pp. 53-75, 2008. [pdf]
• Models and Algorithms for Stochastic Online Scheduling (with M. Uetz and T. Vredeveld)
  Mathematics of Operations Research, Vol. 31, pp. 513-525, 2006. [pdf]
• How to whack moles (with S. Gutiérrez, S.O. Krumke and T. Vredeveld)
  Theoretical Computer Science, Vol. 361, pp. 329-341, 2006. [pdf]
• On-line scheduling to minimize average completion time revisited (with A.S. Schulz)
  Operations Research Letters, Vol. 32, pp. 485-490, 2004. [pdf]

Others

• Robustness and Approximation for Universal Sequencing.
  Gems of Combinatorial Optimization and Graph Algorithms 2015: 133-141.
• Universal Sequencing on an Unreliable Machine (with Julian Mestre)
  Encyclopedia of Algorithms 2016: 2304-2308.
• Keller oder Dach zuerst.
  In K. Biermann, M. Grötschel, and B. Lutz-Westphal, editors, Besser als Mathe: Moderne angewandte Mathematik aus dem Matheon zum Mit- machen, pages 111–115. Vieweg+Teubner, 2009.

Notes

• An Gap example on the (W)SEPT Policy (mit W.C. Cheung, F. Fischer, J. Matuschke), 2014. [pdf]
• Short note on scheduling on a single machine with one non-availability period (with Jose Verschae), 2008. [pdf]

Theses

• Coping with Incomplete Information in Scheduling - Stochastic and Online Models.
  Dissertation, Technische Universität Berlin, 2006. Cuvillier Göttingen, 2007.
• Performance analysis of on-line algorithms in machine scheduling.
  Diploma thesis, Technische Universität Berlin, 2002.

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.