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
- Approximation algorithms
- Uncertainty models: online, stochastic, robust, universal
- Scheduling and resource allocation
- Real-time scheduling
-->
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.
- 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.
- 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.