### Page Content

### to Navigation

## Publications

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]

Bjelde, A., Disser, Y., Hackfeld, J., Hansknecht, C., Lipmann, M., Meißner, J., Schewior, K., Schlöter, M. and Stougie, L.

**Tight bounds for online TSP on the line**.

In *Proceedings of the Symposium on Discrete Algorithms (SODA)*, pp. 994–1005, 2017.
[pdf]

Antoniadis, A., Hoeksma, R., Meißner, J., Verschae, J. and Wiese, A.

**A QPTAS for the General Scheduling Problem with Identical Release Dates**.

In *Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP)*, 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]

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]

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]

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]

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]

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]

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]

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]

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