### Page Content

### to Navigation

# Publications

Journal Conferences Theses Other

## Journal Articles

Megow, N., Meißner, J. and Skutella, M.

**Randomization Helps Computing a Minimum Spanning Tree under Uncertainty**.

*SIAM Journal on Computing*, pp. 1217 - 1240, 2017.
[pdf]

Megow, N., Skutella, M., Verschae, J. and Wiese, A.

**The Power of Recourse for Online MST and TSP**.

*SIAM Journal on Computing*, Vol. 45, pp. 859-880, 2016.

Correa, J. and Megow, N.

**Clique partitioning with value-monotone submodular cost**.

*Discrete Optimization*, Vol. 15, pp. 26-36, 2015.
[pdf]

Megow, N. and Vredeveld, T.

**A Tight 2-Approximation for Preemptive Stochastic Scheduling**.

*Mathematics of Operations Research*, Vol. 39, pp. 1297-1310, 2014.
[pdf]

Günther, E., König, F. G. and Megow, N.

**Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width**.

*Journal of Combinatorial Optimization*, Vol. 27, pp. 164-181, 2014.
[pdf]

Bonifaci, V., Chan, H.-L., Marchetti-Spaccamela, A. and Megow, N.

**Algorithms and Complexity for Periodic Real-Time Scheduling**.

*Transactions on Algorithms*, Vol. 9, pp. 601-619, 2012.
[pdf]

Baruah, S., Bonifaci, V., D'Angelo, G., Li, H., Marchetti-Spaccamela, A., Megow, N. and Stougie, L.

**Scheduling real-time mixed-criticality jobs**.

*IEEE Transactions on Computers*, Vol. 61, pp. 1140-1152, 2012.
[pdf]

Höhn, W., Jacobs, T. and Megow, N.

**On Eulerian extensions and their application to no-wait flowshop scheduling**.

*Journal of Scheduling*, Vol. 15, pp. 295-309, 2012.
[pdf]

Chan, H.-L., Megow, N., Sitters, R. and van Stee, R.

**The offline sorting buffer problem is NP-hard**.

*Theoretical Computer Science*, Vol. 423, pp. 11–18, 2012.
[pdf]

Epstein, L., Levin, A., Mestre, J., Marchetti-Spaccamela, A., Megow, N., Skutella, M. and Stougie, L.

**Universal sequencing on a single unreliable machine**.

*SIAM Journal on Computing*, Vol. 41, pp. 565-586, 2012.
[pdf]

Megow, N., Mehlhorn, K. and Schweitzer, P.

**Online graph exploration: New results on old and new algorithms**.

*Theoretical Computer Science*, Vol. 463, pp. 62-72, 2012.

Special Issue on Theory and Applications of Graph Searching Problems. [pdf]

Megow, N., Möhring, R. H. and Schulz, J.

**Decision Support and Optimization in Shutdown and Turnaround Scheduling**.

*INFORMS J. on Computing*, Vol. 23, pp. 189–204, 2011.
[pdf]

Froyland, G., Koch, T., Megow, N., Duane, E. and Wren, H.

**Optimizing the Landside Operation of a Container Terminal**.

*OR Spectrum*, Vol. 30, pp. 53-75, 2008.
[pdf]

Megow, N., Uetz, M. and Vredeveld, T.

**Models and Algorithms for Stochastic Online Scheduling**.

*Mathematics of Operations Research*, Vol. 31, pp. 513–525, 2006.
[pdf]

Gutiérrez, S., Krumke, S. O., Megow, N. and Vredeveld, T.

**How to whack moles**.

*Theoretical Computer Science*, Vol. 361, pp. 329–341, 2006.
[pdf]

Megow, N. and Schulz, A. S.

**On-line scheduling to minimize average completion time revisited**.

*Operations Research Letters*, Vol. 32, pp. 485-490, 2004.
[pdf]

## Articles in Refereed Conference Proceedings

Marchetti-Spaccamela, A., Megow, N., Schlöter, J., Skutella, M. and Stougie, L.

**On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems**.

In *Proceedings of the 34th IEEE International Parallel and Distributed Processing Symposium*, 2020.

Dürr, C., Erlebach, T., Megow, N. and Meißner, J.

**An Adversarial Model for Scheduling with Testing**.

In *Proceedings of Innovations in Theoretical Computer Science (ITCS)*, 2018.

full version on arXiv with title "Scheduling with Explorable Uncertainty". [pdf]

Focke, J., Megow, N. and Meißner, J.

**Minimum Spanning Tree under Uncertainty in Theory and Experiments**.

In *Proceedings of the Symposium on Experimental Algorithms (SEA)*, 2017.
[pdf]

Abed, F., Chen, L., Disser, Y., Groß, M., Megow, N., Meißner, J., Richter, A. and Rischke, R.

**Scheduling Maintenance Jobs in Networks**.

In *Proceedings of the International Conference on Algorithms and Complexity (CIAC)*, 2017.

full version on arXiv. [pdf]

Chen, L., Megow, N. and Schewior, K.

**An O(log m)-competitive algorithm for online machine minimization**.

In *Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2016.

Chen, L., Megow, N., Rischke, R., Stougie, L. and Verschae, J.

**Optimal Algorithms and a PTAS for Cost-Aware Scheduling**.

In *Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS'15)*, pp. 211–222, 2015.

Chen, L., Megow, N., Rischke, R. and Stougie, L.

**Stochastic and Robust Scheduling in the Cloud**.

In *Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'15)*, pp. 175–186, 2015.

Megow, N., Meißner, J. and Skutella, M.

**Randomization Helps Computing a Minimum Spanning Tree Under Uncertainty**.

In *Proceedings of the European Symposium on Algorithms (ESA)*, 2015.
[pdf]

Disser, Y., Megow, N., Klimm, M. and Stiller, S.

**Packing a Knapsack of Unknown Capacity**.

In *Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS)*, pp. 276–287, 2014.
[pdf]

Megow, N. and Verschae, J.

**Dual techniques for scheduling on a machine with varying speed**.

In *Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013)*, Lecture Notes in Computer Science, Vol. 7965, pp. 745–756, Springer-Verlag Berlin Heidelberg, 2013.
[pdf]

Bonifaci, V., Marchetti-Spaccamela, A., Megow, N. and Wiese, A.

**Polynomial-time exact schedulability tests for harmonic real-time tasks**.

In *Proceedings of the 34th IEEE Real-Time Systems Symposium (RTSS 2013)*, pp. 236-245, 2013.
[pdf]

Günther, E., Maurer, O., Megow, N. and Wiese, A.

**A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio**.

In *Proceedings of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)*, pp. 118-128, 2013.
[pdf]

Megow, N. and Mestre, J.

**Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints**.

In *Proceedings of the 4th Innovations in Theoretical Computer Science (ITCS 2013)*, pp. 495-504, 2013.
[pdf]

Megow, N., Skutella, M., Verschae, J. and Wiese, A.

**The Power of Recourse for Online MST and TSP**.

In *Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012)*, Lecture Notes in Computer Science, Vol. 7391, pp. 689–-700, Springer, 2012.
[pdf]

Megow, N., Mehlhorn, K. and Schweitzer, P.

**Online Graph Exploration: New Results on Old and New Algorithms**.

In *Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)*, Lecture Notes in Computer Science, Vol. 6756, pp. 478–489, Springer, 2011.
[pdf]

Anand, S., Garg, N. and Megow, N.

**Meeting deadlines: How much speed suffices?**.

In *Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)*, Lecture Notes in Computer Science, Vol. 6755, pp. 232–243, Springer, 2011.
[pdf]

Günther, E., König, F. G. and Megow, N.

**Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width**.

In *Approximation and Online Algorithms: 7th International Workshop, WAOA 2009*, Lecture Notes in Computer Science, Vol. 5893, pp. 170-181, Springer, 2010.
[pdf]

Baruah, S., Bonifaci, V., D'Angelo, G., Li, H., Marchetti-Spaccamela, A., Megow, N. and Stougie, L.

**Scheduling real-time mixed-criticality jobs**.

In *Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010)*, Lecture Notes in Computer Science, Vol. 6281, pp. 90–101, Springer, 2010.
[pdf]

Bonifaci, V., Chan, H.-L., Marchetti-Spaccamela, A. and Megow, N.

**Algorithms and Complexity for Periodic Real-Time Scheduling**.

In *Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, pp. 1350–1359, 2010.
[pdf]

Günther, E., König, F. G. and Megow, N.

**The Bin Scheduling Problem**.

In *Proceedings of the 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009)*, 2009.
[pdf]

Correa, J. R., Megow, N., Raman, R. and Suchan, K.

**Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs**.

In *8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009)*, 2009.
[pdf]

Megow, N., Möhring, R. H. and Schulz, J.

**Turnaround Scheduling in Chemical Manufacturing**.

In *Proceedings of the 8th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2007)*, 2007.

Megow, N. and Vredeveld, T.

**Approximation in Preemptive Stochastic Online Scheduling**.

In *Proceedings of 14th European Symposium on Algorithms (ESA'06)*, Lecture Notes in Computer Science, Vol. 4168, pp. 516–527, Springer, 2006.

Heinz, S., Krumke, S. O., Megow, N., Rambau, J., Tuchscherer, A. and Vredeveld, T.

**The Online Target Date Assignment Problem**.

In *Approximation and Online Algorithms (WAOA'05)*, Lecture Notes in Computer Science, Vol. 3879, pp. 192-205, Springer, 2006.
[pdf]

Megow, N., Uetz, M. and Vredeveld, T.

**Stochastic Online Scheduling on Parallel Machines**.

In *Approximation and Online Algorithms (WAOA'04)*, Lecture Notes in Computer Science, Vol. 3351, pp. 167-180, Springer, 2005.
[pdf]

Krumke, S. O., Megow, N. and Vredeveld, T.

**How to Whack Moles**.

In *Approximation and Online Algorithms (WAOA'03)*, Lecture Notes in Computer Science, Vol. 2909, pp. 192–205, Springer, 2004.

Megow, N. and Schulz, A. S.

**Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line Algorithms**.

In *Approximation and Online Algorithms (WAOA'03)*, Lecture Notes in Computer Science, Vol. 2909, pp. 227–234, Springer, 2004.

## Theses

Megow, N.

**Coping with Incomplete Information in Scheduling - Stochastic and Online Models**.

PhD thesis, TU Berlin, 2006.
[pdf]

Megow, N.

**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.