Homepage

Nicole Megow

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Building 46.1, Room 318
Campus E1 4
66123 Saarbrücken
Germany

Email: nmegow@mpi-inf.mpg.de
Phone: +49 681 9325 118
Fax: +49 681 9325 199

Research Interests

Approximation algorithms
Uncertainty models: online, stochastic, robust, universal
Scheduling and resource allocation
Real-time scheduling

Current activities

Organization of the 10th Max-Planck Advanced Course on the Foundations of Computer Science (ADFOCS), September 2009.

-->

Teaching

Summer 2010: Optimization (with Kurt Mehlhorn and Julian Mestre) at Saarland University
Summer 2009: Seminar on Optimization under Uncertainty: Stochastic and Online Models (with Rob van Stee) at Saarland University
Winter 2008/09: Approximation Algorithms (with Spyros Angelopoulos and Rajiv Raman) at Saarland University
Winter 2007/08: Online Optimierung (with Guido Schäfer) at TU Berlin
Summer 2003: PhD course Advanced Combinatorial Algorithms (with Sven O. Krumke) at Escuela Politecnica Nacional in Quito, Ecuador, within a DAAD granted programme

Publications

Submitted

Nicole Megow and Tjark Vredeveld.
Approximating Preemptive Stochastic Scheduling, 2009. METEOR Research Memorandum RM/09/054, Maastricht University.
Wiebke Höhn, Tobias Jacobs, and Nicole Megow.
Flowshop Scheduling with Respect to Machine Idle Times, 2009. [pdf]
Nicole Megow, Rolf H. Möhring, and Jens Schulz.
Decision Support and Optimization in Shutdown and Turnaround Scheduling, 2009. Preprint 009/2009, TU Berlin.
Nicole Megow and Tjark Vredeveld.
Stochastic Online Scheduling with Precedence Constraints, 2008. [pdf]

Papers in Refereed Journals and Conference Proceedings

L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, and L. Stougie.
Universal sequencing on a single machine.
In Proc. of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010), 2010.
Vincenzo Bonifaci, Ho-Leung Chan, Alberto Marchetti-Spaccamela, and Nicole Megow.
Algorithms and Complexity for Periodic Real-Time Scheduling. [pdf]
In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 1350-1359, 2010.
Elisabeth Günther, Felix G. König, and Nicole Megow.
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width. [pdf]
In Proc. of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009), to appear 2010.
Jose R. Correa, Nicole Megow, Rajiv Raman, and Karol Suchan.
Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs [pdf]
In 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009), Paris, France, 2009.
Gary Froyland, Thorsten Koch, Nicole Megow, Emily Duane, and Howard Wren.
Optimizing the Landside Operation of a Container Terminal. [pdf]
OR Spectrum 30(1):53-75, 2008.
Nicole Megow.
Coping with incomplete information in scheduling - stochastic and online models. [pdf]
In Operations Research, Springer, pages 17-22, 2008. Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Saarbrücken, September 5-7, 2007.
Nicole Megow, Marc Uetz, and Tjark Vredeveld.
Models and Algorithms for Stochastic Online Scheduling. [pdf]
Mathematics of Operations Research 31(3): 513--525, 2006.
Nicole Megow and Tjark Vredeveld.
Approximation in Preemptive Stochastic Online Scheduling. [pdf]
In Proc. of the 14th European Symposium on Algorithms (ESA 2006), LNCS 4168, pages 516-527, 2006.
Sandra Gutierrez, Sven O. Krumke, Nicole Megow, and Tjark Vredeveld.
How to Whack Moles. [pdf]
Theoretical Computer Science 361: 329-341, 2006.
Stefan Heinz, Jörg Rambau, Sven O. Krumke, Nicole Megow, Andreas Tuchscherer, and Tjark Vredeveld.
The Online Target Date Assignment Problem. [pdf]
In Proc. of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), LNCS 3879, pages 230-243, 2006.
Nicole Megow, Marc Uetz, and Tjark Vredeveld.
Stochastic Online Scheduling on Parallel Machines. [pdf]
In Proc. of the 2nd Workshop on Approximation and Online Algorithms (WAOA 2004), LNCS 3351, pages 167-180, 2005.
Nicole Megow and Andreas S. Schulz.
On-line scheduling to minimize average completion time revisited. [pdf]
Operations Research Letters 32: 485-490, 2004.
Sven O. Krumke, Nicole Megow, and Tjark Vredeveld.
How to Whack Moles. [pdf]
In Proc. of the First Workshop on Approximation and Online Algorithms (WAOA 2003), LNCS 2909, pages 192-205, 2004.
Nicole Megow and Andreas S. Schulz.
Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line Algorithms.
In Proc. of the First Workshop on Approximation and Online Algorithms (WAOA 2003), LNCS 2909, pages 227-234, 2004.

Theses

Coping with Incomplete Information in Scheduling - Stochastic and Online Models. [pdf]
PhD thesis (Dissertation), Technische Universität Berlin, Germany, October 2006.
Awarded with the GOR Dissertation Prize 2007.
Published by Cuvillier Verlag Göttingen, Germany, 2007.
Performance analysis of on-line algorithms in machine scheduling.
Master's thesis (Diplomarbeit), Technische Universität Berlin, Germany, April 2002.

Other Publications (not included above)

Nicole Megow.
Keller oder Dach zuerst.
In Besser als Mathe: Moderne angewandte Mathematik aus dem MATHEON zum Mitmachen, K. Biermann, M. Götschel, and B. Lutz-Westphal (eds.), Vieweg+Teubner, 2009.
Alberto Marchetti-Spaccamela, Nicole Megow, Martin Skutella, and Leen Stougie.
Robust sequencing on a single machine, 2009. Matheon Preprint 557.
Short abstract appeared as:
Price of Robustness in Single Machine Scheduling in Proc. of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), Abbey Rolduc, The Netherlands, 2009.
Wiebke Höhn, Tobias Jacobs, and Nicole Megow.
On Eulerian Extension Problems and their Application to Sequencing Problems. Preprint 008/2009, TU Berlin, 2009.
Abstract in Proc. of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), Abbey Rolduc, The Netherlands, 2009.
Elisabeth Günther, Felix G. König, and Nicole Megow.
The Bin Scheduling Problem. [pdf]
In Proc. of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009), Abbey Rolduc, The Netherlands, 2009.
Nicole Megow and Jose Verschae.
Short Note on Scheduling on a Single Machine with one Non-availability Period.
Matheon Preprint 533, 2008. [pdf]
Nicole Megow, Rolf H. Möhring, and Jens Schulz.
Turnaround scheduling in chemical manufacturing. [pdf]
Selected for plenary talk.
In Proc. of the 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2007), Istanbul, Turkey, 2007.
Gary Froyland, Thorsten Koch, Nicole Megow, Andre Costa, and Emily Duane.
Finding the Strategic Corridor. Final report on the pilot project regarding control and optimising of the new automated RMG based road/rail exchange area at Patrick's Port Botany container terminal.
Project report, 2005.

Recent Positions

Since March 2008:
Postdoctoral researcher at the Max Planck Institute for Informatics, Saarbrücken, Germany, in the group Algorithms and Complexity of Kurt Mehlhorn.
April - May 2008:
Visiting researcher at Centro de Modelamiento Matemático (CMM) at Universidad de Chile, Santiago de Chile. Visiting José R. Correa.
October 2002 - February 2008:
Research assistent at Technische Universität Berlin, Germany, within the group Combinatorial Optimization and Graph Algorithms of Rolf H. Möhring.
Member of the DFG Research Center MATHEON within the project Optimization under uncertainty in logistics and scheduling.
August - October 2005:
Visiting researcher at the University of New South Wales, Sydney, Australia. Visiting Gary Froyland for a joint MATHEON and MASCOS Project with Patrick Corporation, Sydney, on optimizing the landside operation of the container terminal Port Botany Bay in Sydney.

Education

October 2002 - December 2006:
Ph. D. student at Technische Universität Berlin, Germany. Ph. D. (Dr. rer. nat) in Mathematics.
Thesis: Coping with Incomplete Information in Scheduling: Stochastic and Online Models, supervised by Rolf H. Möhring.
Awarded with the Dissertation Prize 2007 of the German Operations Research Society (GOR).
October 1996 - July 2002:
Student in a joint program of mathematics, economics and computer science (Wirtschaftsmathematik)
at Technische Universität Berlin, Germany. Master's degree (Dipl.-Math. oec.).
April 2001 - April 2002:
Visiting student at the Operations Research Center at Massachusetts Institute of Technology (MIT).
Thesis: Performance analysis of on-line algorithms in machine scheduling, under supervision of Andreas S. Schulz.
June 1996:
Abitur at the Alexander-von-Humboldt Oberschule, Berlin.

Offers

We are constantly looking for excellent PhD students and Postdocs. See AG1 offers for more details.