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

In winter 2011/12 I am at Technische Universität Darmstadt as a guest professor for Discrete Optimization.

The First Interdisciplinary Workshop on Algorithmic Challenges in Real-Time Systems will take place February 27-29, 2012, in Berlin.

Research Interests

Combinatorial optimization, approximation algorithms
Uncertainty models: online, stochastic, robust, universal
Scheduling, resource allocation, routing

Publications

Submitted

Elisabeth Günther, Olaf Maurer, Nicole Megow, and Andreas Wiese.
A New Approach to Competitive Analysis: Approximating the Optimal Competitive Ratio, 2011.
L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, and L. Stougie.
Universal sequencing on an unreliable machine, 2011. [pdf]
(Full version of paper at IPCO 2010 with extensions to generalized cost functions.)
José R. Correa and Nicole Megow.
Clique partitioning with value-monotone submodular cost, 2011.
Nicole Megow and Tjark Vredeveld.
Approximating Preemptive Stochastic Scheduling, 2009. METEOR Research Memorandum RM/09/054, Maastricht University.

Articles in Refereed Conference Proceedings

S. Anand, Naveen Garg, and Nicole Megow.
Meeting deadlines: How much speed suffices? [pdf]
In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 6755, pages 232-243, Springer, 2011.
Nicole Megow, Kurt Mehlhorn, and Pascal Schweitzer.
Online Graph Exploration: New Results on Old and New Algorithms. [pdf]
In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 6756, pages 478-489, Springer, 2011.
S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, and L. Stougie.
Scheduling real-time mixed-criticality jobs. [pdf]
In Proc. of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), LNCS 6281, pages 90-101. Springer, 2010.
L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, and L. Stougie.
Universal sequencing on a single machine. [pdf]
In Proc. of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010), LNCS 6080, pages 230-243. Springer, 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), LNCS 5893, pages 170-181. Springer, 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.
Nicole Megow.
Coping with incomplete information in scheduling - stochastic and online models. [pdf]
In Operations Research Proceedings, Springer, pages 17-22, 2008.
Invited submission for winner of the Dissertation Award of the German Operations Research Society (GOR).
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.
Preprint of full version: METEOR Research Memorandum RM/09/054, 2009.
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.
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.

Journal Articles

Ho-Leung Chan, Nicole Megow, Rob van Stee, and René Sitters.
The Sorting Buffer Problem is NP-hard, 2010. [arxiv]
Theoretical Computer Science, accepted for publication, 2012.
S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, and L. Stougie.
Scheduling real-time mixed-criticality jobs.
IEEE Transactions on Computers, accepted for publication, 2011.
Wiebke Höhn, Tobias Jacobs, and Nicole Megow.
On Eulerian extensions and their application to no-wait flowshop scheduling. [pdf]
Journal of Scheduling, Online First, pp. 1-15, 2011. DOI: 10.1007/s10951-011-0241-1.
Nicole Megow, Rolf H. Möhring, and Jens Schulz.
Decision Support and Optimization in Shutdown and Turnaround Scheduling. [pdf]
INFORMS Journal on Computing 23(2): 189-204, 2011.
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, Marc Uetz, and Tjark Vredeveld.
Models and Algorithms for Stochastic Online Scheduling. [pdf]
Mathematics of Operations Research 31(3): 513-525, 2006.
Sandra Gutierrez, Sven O. Krumke, Nicole Megow, and Tjark Vredeveld.
How to Whack Moles. [pdf]
Theoretical Computer Science 361: 329-341, 2006.
Nicole Megow and Andreas S. Schulz.
On-line scheduling to minimize average completion time revisited. [pdf]
Operations Research Letters 32: 485-490, 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 Tjark Vredeveld.
Stochastic Online Scheduling with Precedence Constraints. [pdf]
Matheon Preprint, 2008.
Nicole Megow and Jose Verschae.
Short Note on Scheduling on a Single Machine with one Non-availability Period. [pdf]
Matheon Preprint, 2008.
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.

Teaching

Winter 2011: Einführung in die Optimierung at TU Darmstadt.
Winter 2011: Seminar on Proofs from the BOOK at TU Darmstadt.
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

Recent Positions

October 2010 - March 2011:
Guest professor for Discrete Optimization at Technische Universität Darmstadt.
Since December 2011:
Senior researcher at the Max-Planck-Institut für Informatik, Saarbrücken, Germany.
March 2008 - November 2011:
Research associate at the Max-Planck-Institut für Informatik, Saarbrücken, Germany.
April - May 2008:
Visiting researcher at Centro de Modelamiento Matemático (CMM) at Universidad de Chile, Santiago de Chile.
October 2002 - February 2008:
Research assistent at Technische Universität Berlin, Germany,the group Combinatorial Optimization and Graph Algorithms.
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.

Activities

Organisation of the First Interdisciplinary Workshop on Algorithmic Challenges in Real-Time Systems (with Sebastian Stiller and Marko Bertogna), February 2012.
Member of the Program Committee of CATS 2012.
Organization of the 10th Max-Planck Advanced Course on the Foundations of Computer Science (ADFOCS), September 2009.
Member of the Program Committee of MAPSP 2009.

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.