High Profile Area at the

logo-mmm-w
logo-mmm-w
Nicole Megow
Prof. Nicole Megow
  • Faculty: Faculty 3 - Mathematics & Computer Science
  • Subject area:Combinatorial optimization, efficient algorithms, optimization under uncertainty, applications in production and logistics
  • Office: MZH 3210

Further information:

Combinatorial Optimization and Logistics group

Ecosystem

Member of the research focus "Minds, Media, Machines"
Member of the Data Science Center (DSC)
Member of the Board of Directors of the "Logdynamics" research cluster
The Chair of Combinatorial Optimization in the Department of Mathematics and Computer Science at the University of Bremen
Publications
2017 // Journal article

Packing a knapsack of unknown capacity

SIAM Journal on Discrete Mathematics

Disser, Y.; Klimm, M.; Megow, N.; Stiller, S.
https://doi.org/10.1137/16M1070049
2017 // Journal article

Randomization helps computing a minimum spanning tree under uncertainty

SIAM Journal on Computing

Megow, N.; Meißner, J.; Skutella, M.
https://doi.org/10.1137/16M1088375
2017 // Book

Scheduling maintenance jobs in networks

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Abed, F.; Chen, L.; Disser, Y.; Groß, M.; Megow, N.; Meißner, J.; Richter, A.T.; Rischke, R.
https://doi.org/10.1007/978-3-319-57586-5_3
2016 // Journal article

A new approach to online scheduling: Approximating the optimal competitive ratio

ACM Transactions on Algorithms

L�bbecke, E.; Maurer, O.; Megow, N.; Wiese, A.
https://doi.org/10.1145/2996800
2016 // Conference paper

An O(log n)-competitive algorithm for online machine minimization

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Chen, L.; Megow, N.; Schewior, K.
http://www.scopus.com/inward/record.url?eid=2-s2.0-84962920222&partnerID=MN8TOARS
2016 // Journal article

Guest editors' foreword

Theory of Computing

Megow, N.; Wootters, M.
https://doi.org/10.4086/toc.2016.v012a013
2016 // Book chapter

Robustness and approximation for universal sequencing

Gems of Combinatorial Optimization and Graph Algorithms

Megow, N.
https://doi.org/10.1007/978-3-319-24971-1_13
2016 // Conference paper

The power of migration in online machine minimization

Annual ACM Symposium on Parallelism in Algorithms and Architectures

Chen, L.; Megow, N.; Schewior, K.
https://doi.org/10.1145/2935764.2935786
2015 // Journal article

Clique partitioning with value-monotone submodular cost

Discrete Optimization

Correa, J.R.; Megow, N.
https://doi.org/10.1016/j.disopt.2014.11.001
2015 // Book

Optimal algorithms and a PTAS for cost-aware scheduling

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Chen, L.; Megow, N.; Rischke, R.; Stougie, L.; Verschae, J.
https://doi.org/10.1007/978-3-662-48054-0_18
2015 // Book

Randomization helps computing a minimum spanning tree under uncertainty

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Megow, N.; Meißner, J.; Skutella, M.
https://doi.org/10.1007/978-3-662-48350-3_73
2015 // Conference paper

Stochastic and robust scheduling in the cloud

Leibniz International Proceedings in Informatics, LIPIcs

Chen, L.; Megow, N.; Rischke, R.; Stougie, L.
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.175
2014 // Journal article

A tight 2-approximation for preemptive stochastic scheduling

Mathematics of Operations Research

Megow, N.; Vredeveld, T.
https://doi.org/10.1287/moor.2014.0653
2014 // Book

Packing a knapsack of unknown capacity

Leibniz International Proceedings in Informatics, LIPIcs

Disser, Y.; Klimm, M.; Megow, N.; Stiller, S.
https://doi.org/10.4230/LIPIcs.STACS.2014.276
2014 // Journal article

Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width

Journal of Combinatorial Optimization

Günther, E.; König, F.G.; Megow, N.
https://doi.org/10.1007/s10878-012-9498-3
2013 // Conference paper

A new approach to online scheduling: Approximating the optimal competitive ratio

Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Günther, E.; Maurer, O.; Megow, N.; Wiese, A.
http://www.scopus.com/inward/record.url?eid=2-s2.0-84876026066&partnerID=MN8TOARS
2013 // Book

Dual techniques for scheduling on a machine with varying speed

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Megow, N.; Verschae, J.
https://doi.org/10.1007/978-3-642-39206-1_63
2013 // Conference paper

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

ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science

Megow, N.; Mestre, J.
https://doi.org/10.1145/2422436.2422490
2013 // Conference paper

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

Proceedings - Real-Time Systems Symposium

Bonifaci, V.; Marchetti-Spaccamela, A.; Megow, N.; Wiese, A.
https://doi.org/10.1109/RTSS.2013.31
2012 // Journal article

A note on sorting buffers offline

Theoretical Computer Science

Chan, H.-L.; Megow, N.; Sitters, R.; Van Stee, R.
https://doi.org/10.1016/j.tcs.2011.12.077
2012 // Journal article

Algorithms and complexity for periodic real-time scheduling

ACM Transactions on Algorithms

Bonifaci, V.; Chan, H.-L.; Marchetti-Spaccamela, A.; Megow, N.
https://doi.org/10.1145/2390176.2390182
2012 // Journal article

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

Journal of Scheduling

Höhn, W.; Jacobs, T.; Megow, N.
https://doi.org/10.1007/s10951-011-0241-1
2012 // Journal article

Online graph exploration: New results on old and new algorithms

Theoretical Computer Science

Megow, N.; Mehlhorn, K.; Schweitzer, P.
https://doi.org/10.1016/j.tcs.2012.06.034
2012 // Journal article

Scheduling real-time mixed-criticality jobs

IEEE Transactions on Computers

Baruah, S.; Bonifaci, V.; D'Angelo, G.; Li, H.; Marchetti-Spaccamela, A.; Megow, N.; Stougie, L.
https://doi.org/10.1109/TC.2011.142
2012 // Book

The power of recourse for online MST and TSP

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Megow, N.; Skutella, M.; Verschae, J.; Wiese, A.
https://doi.org/10.1007/978-3-642-31594-7_58