![[Translate to English:]](/fileadmin/user_upload/fachbereiche/fb3/infcon/CSLog/CSLog.png)
Nicole Megow's Publications
2024
The Power of Proportional Fairness for Non-Clairvoyant Scheduling under Polyhedral Constraints arxiv.org
Sven Jäger, Alexander Lindermayr, Nicole Megow
SODA 2025
Accelerating Matroid Optimization through Fast Imprecise Oracles arxiv.org
Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr, Zhenwei Liu, Nicole Megow, Jens Schlöter
NeurIPS 2024
The Safe and Effective Use of Optimistic Period Predictions
Sanjoy Baruah, Pontus Ekberg, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie
RTNS 2024
Competitive Query Minimization for Stable Matching with One-Sided Uncertainty, arxiv.org
Evripidis Bampis, Konstantinos Dogeas, Thomas Erlebach, Nicole Megow, Jens Schlöter, Amitabh Trehan
APPROX 2024
Solution discovery via reconfiguration for problems in P
arxiv.org, LIPIcs
Mario Grobler, Stephanie Maaz, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Daniel Schmand, Sebastian Siebertz
ICALP 2024
Fast Combinatorial Algorithms for Efficient Sortation arxiv.org
Madison Van Dyk, Jochen Koenemann, Nicole Megow, Kim Klause
IPCO 2024
Santa Claus meets Makespan and Matroids: Algorithms and Reductions arxiv.org
Étienne Bamas, Alexander Lindermayr, Nicole Megow, Lars Rohwedder, Jens Schlöter
SODA 2024
2023
On Solution Discovery via Reconfiguration arxiv.org DOI
Michael R. Fellows, Mario Grobler, Nicole Megow, Amer E. Mouawad, Vijayaragunathan Ramamoorthi, Frances A. Rosamond, Daniel Schmand, Sebastian Siebertz
ECAI 2023: 700-707.
Speed-Oblivious Online Scheduling: Knowing (Precise) Speeds is not Necessary arxiv.org DOI
Alexander Lindermayr, Nicole Megow, Martin Rapp
ICML 2023: 21312-21334.
Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints arxiv.org PMLR
Alexandra Lassota, Alexander Lindermayr, Nicole Megow, Jens Schlöter
ICML 2023: 18563-18583.
Matching Augmentation via Simultaneous Contractions arxiv DOI
Mohit Garg, Felix Hommelsheim, Nicole Megow
ICALP 2023: 65:1-65:17.
Sorting and Hypergraph Orientation under Uncertainty with Predictions arxiv.org DOI
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter
IJCAI 2023: 5577-5585.
Configuration Balancing for Stochastic Requests arxiv DOI
Franziska Eberle, Anupam Gupta, Nicole Megow, Benjamin Moseley, Rudy Zhou
IPCO 2023: 127-141.
Set Selection under Explorable Stochastic Uncertainty via Covering Techniques arxiv DOI
Nicole Megow and Jens Schlöter
IPCO 2023: 319-333.
Speed-Robust Scheduling: Sand, Bricks, and Rocks arxiv springer
Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon
Mathematical Programming: 197(2), 1009-1048, 2023.
Online Throughput Maximization on Unrelated Machines: Commitment is No Burden arxiv acm
Franziska Eberle, Nicole Megow, and Kevin Schewior.
ACM Transactions on Algorithms: 19(1), 10:1–10:25, 2023.
2022
A Universal Error Measure for Input Predictions Applied to Online Graph Problems arxiv.org NeurIPS
Giulia Bernardini, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie, Michelle Sweering
NeurIPS 2022
Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty arxiv.org DOI
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter
ESA 2022: 49:1-49:18
Throughput Scheduling with Equal Additive Laxity sciencedirect.com
Martin Böhm, Nicole Megow, Jens Schlöter
Oper. Res. Lett. 50(5): 463-469 (2022)
On Hop-Constrained Steiner Trees in Tree-Like Metrics arxiv.org siam.org pdf
M. Böhm, R. Hoeksma, N. Megow, L. Nölke and B. Simon
SIAM J. Discrete Mathematics 36(2):1249-1273, 2022.
Non-clairvoyant Scheduling with Predictions Revisited arxiv.org
Alexander Lindermayr and Nicole Megow
SPAA 2022
Online load balancing with general reassignment cost pdf sciencedirect.com
Sebastian Berndt, Franziska Eberle, Nicole Megow
Operations Research Letters 50(3): 322-328, 2022
Robustification of Online Graph Exploration Methods arxiv.org DOI
Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, Jens Schlöter
AAAI 2022: 9732-9740
Double Coverage with Machine-Learned Advice arxiv.org ITCS
Alexander Lindermayr, Nicole Megow, Bertrand Simon
ITCS 2022: 99:1-99:18
2021
Explorable Uncertainty Meets Decision-Making in Logistics springer.com
Nicole Megow and Jens Schlöter
Dynamics in Logistics: 35-56, 2021 springer.com
Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time arxiv.org DOI
Franziska Eberle, Nicole Megow, Lukas Nölke, Bertrand Simon, Andreas Wiese
FSTTCS 2021: 18:1-18:17
Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty pdf
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter
ESA 2021: 10:1-10:18
Optimal Algorithms for Scheduling under Time-of-Use Tariffs pdf DOI
Lin Chen, Nicole Megow, Roman Rischke, Leen Stougie and Jose Verschae
Annals or Operations Research 304(1): 85-107, 2021
Throughput Scheduling with Equal Additive Laxity springer.com
Martin Böhm, Nicole Megow, Jens Schlöter
CIAC 2021: 130-143
Speed-Robust Scheduling arxiv.org DOI
Franziska Eberle, Ruben Hoeksma, Nicole Megow, Lukas Nölke, Kevin Schewior, Bertrand Simon
IPCO 2021: 283-296
2020
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments DOI
Jacob Focke, Nicole Megow, Julie Meißner
ACM Journal of Experimental Algorithmics 25(1), Article 1.14, 2020
Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics PDF DOI
M. Böhm, R. Hoeksma, N. Megow, L. Nölke and B. Simon
In Proc. of the 45th International Symposium on Mathematical Foundations of Computer Science 18:1-18:15 (MFCS2020)
An Adversarial Model for Scheduling with Testing DOI
Christoph Dürr, Thomas Erlebach, Nicole Megow and Julie Meißner
Algorithmica 82(12): 3630-3675, 2020
Online Minimum Cost Matching with Recourse on the Line PDF DOI
N. Megow and L. Nölke.
In Proc. of the 23rd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems 37:1-37:16 (APPROX 2020)
Optimally Handling Commitment Issues in Online Throughput Maximization pdf dagstuhl.de
F. Eberle, N. Megow, and K. Schewior.
Proceedings of ESA 2020, pp. 41:1-41:15, 2020.
On the Complexity of Conditional DAG Scheduling in Multiprocessor Systems PDF ieee.org
A. Marchetti-Spaccamela, N. Megow, J. Schlöter, M. Skutella, and L. Stougie
Proceedings of IPDPS 1061-1070, 2020
A General Framework for Handling Commitment in Online Throughput Maximization pdf springer.com
L. Chen, F. Eberle, N. Megow, K. Schewior, and C. Stein.
Mathematical Programming 183(1): 215-247, 2020
2019
A General Framework for Handling Commitment in Online Throughput Maximization pdf springer.com
L. Chen, F. Eberle, N. Megow, K. Schewior, C. Stein.
Proceedings of IPCO 2019, pp. 141-154, 2019.
Scheduling Self-Suspending Tasks: New and Old Results
J.J. Chen, R. Hoeksma, T. Hahn, N. Megow, G. von der Brueggen
Proceedings of ECRTS, 16:1-16:23, 2019.
On Index Policies for Stochastic Minsum Scheduling sciencedirect.com
F. Eberle, F. Fischer, J. Matuschke, N. Megow
Operations Research Letters, 47(3): 213-218, 2019.
Scheduling Maintenance Jobs in Networks PDF
F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, N. Megow, A.T. Richter, R. Rischke
Theoretical Computer Science 754: 107-121, 2019. Special issue of STACS (invited).
2018
Scheduling with Explorable Uncertainty PDF springer.com
C. Dürr, T. Erlebach, J. Meißner and N. Megow.
In Proc. of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), 30:1-30:14, 2018.
An O(log m)-Competitive Algorithm for Online Machine Minimization PDF siam.org
L. Chen, N. Megow, K. Schewior
SIAM Journal on Computing 47(6), 2057–2077, 2018.
Dual techniques for scheduling on a machine with varying speed PDF siam.org
N. Megow, J. Verschae
SIAM Journal on Discrete Mathematics 32(3): 1541-1571, 2018.
2017
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments PDF
J. Focke, J. Meißner, N. Megow
In Proc. of the 16th International Symposium on Experimental Algorithms (SEA 2017), LIPIcs, Article No. 22; pp. 22:1–22:14, 2017.
Scheduling Maintenance Jobs in Networks PDF
F. Abed, L. Chen, Y. Disser, M. Groß, J. Meißner, N. Megow, A.T. Richter and R. Rischke
In Proc. of the 10th International Conference on Algorithms and Complexity (CIAC 2017), LNCS 10236, pp. 19–30, 2017.
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty PDF
J. Meißner, N. Megow, M. Skutella
SIAM Journal on Computing 46(4): 1217-1240, 2017.
Packing a Knapsack of Unknown Capacity PDF
Y. Disser, M. Klimm, N. Megow, S. Stiller
SIAM Journal on Discrete Mathematics 31(3): 1477-1497, 2017.
2016
Universal Sequencing on an Unreliable Machine
N. Megow, Julian Mestre
Encyclopedia of Algorithms 2016: 2304-2308.
The Power of Migration in Online Machine Minimization PDF
L. Chen, N Megow and K. Schewior
In Proc. of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016), pp. 175-184, 2016.
An O(log m)-Competitive Algorithm for Online Machine Minimization PDF
L. Chen, N. Megow and K. Schewior
In Proc. of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 155-163, 2016.
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio
E. Lübbecke, O. Maurer, N. Megow, A. Wiese
ACM Transactions on Algorithms 13(1), pp. 15:1-15:34, 2016.
The Power of Recourse for Online MST and TSP PDF
N. Megow, M. Skutella, J. Verschae, A. Wiese
SIAM Journal on Computing. 45-3, pp. 859-880, 2016
Universal Sequencing on an Unreliable Machine
N. Megow, Julian Mestre
Encyclopedia of Algorithms 2016: 2304-2308.
2015
Randomization Helps Computing a Minimum Spanning Tree under Uncertainty PDF
J. Meißner, N. Megow and M. Skutella
In Proc. of the 23rd European Symposium on Algorithms (ESA 2015), LNCS 9294, pp. 878-890, Springer, 2015.
Stochastic and Robust Scheduling in the Cloud PDF
L. Chen, N. Megow, R. Rischke and L. Stougie
In Proc. of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015), LIPIcs 40, pp. 175-186, 2015.
Optimal Algorithms and a PTAS for Cost-Aware Scheduling
L. Chen, n. Megow, R. Rischke, L. Stougie and J. Verschae
In Proc. of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015), LNCS 9235, pp. 211-222, 2015.
Packing a Knapsack of Unknown Capacity PDF
Y. Disser, M. Klimm, N. Megow, S. Stiller
In Proc. of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2015), pp. 276-287, 2015
Meeting deadlines: How much speed suffices? PDF PDF
S. Anand, N. Garg, N. Megow
In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), LNCS 6755, pages 232-243, Springer, 2011.
Erratum for "Meeting deadlines: How much speed suffices?", 2015.
Clique partitioning with value-monotone submodular cost PDF
J. Correa, N. Megow
Discrete Optimization, Vol. 15, pp. 26-36, 2015.
Robustness and Approximation for Universal Sequencing
Gems of Combinatorial Optimization and Graph Algorithms 2015: 133-141.
2014
Scheduling and Packing Malleable and Parallel Tasks with Precedence Constraints of Bounded Width PDF
E. Günther, F. König, N. Megow
Journal of Combinatorial Optimization, Vol. 27, pp. 164-181, 2014.
A Tight 2-Approximation for Preemptive Stochastic Scheduling PDF
N. Megow, T. Vredeveld
Mathematics of Operations Research, Vol. 39, pp. 1297-1310, 2014
An Gap example on the (W)SEPT Policy
W.C. Cheung, F. Fischer, J. Matuschke, N. Megow
2014.
2013
Polynomial-time exact schedulability tests for harmonic real-time tasks PDF
V. Bonifaci, A Marchetti-Spaccamela, N. Megow, A. Wiese
In Proc. of the 34th IEEE Real-Time Systems Symposium (RTSS 2013), pp. 236-245, 2013.
Dual techniques for scheduling on a machine with varying speed PDF
N. Megow, J. Verschae
In Proc. of the 40th International Colloquium on Automata, Languages and Programming (ICALP 2013), LNCS 7965, pp. 745-756, Springer, 2013.
Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints PDF
N. Megow, J. Mestre
In Proc. of the 4th Conference on Innovations in Theoretical Computer Science (ITCS 2013), pp. 495-504, 2013.
A New Approach to Online Scheduling: Approximating the Optimal Competitive Ratio PDF
E. Günther, O. Maurer, N. Megow, A. Wiese
In Proc. of the 24st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), pp. 118-128, 2013.
2012
The Power of Recourse for Online MST and TSP
N. Megow, M. Skutella, J. Verschae, A. Wiese
In Proc. of the 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), LNCS 7391, pages 689-700, Springer, 2012.
On Eulerian extensions and their application to no-wait flowshop scheduling PDF
W. Höhn, T. Jacobs, N. Megow
Journal of Scheduling, Vol. 15, pp. 295-309, 2012.
Algorithms and Complexity for Periodic Real-Time Scheduling PDF
V. Bonifaci, H.-L. Chan, A. Marchetti-Spaccamela
ACM Transactions on Algorithms, Vol. 9, pp. 601-619, 2012.
Scheduling real-time mixed-criticality jobs PDF1 PDF2
S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, Stougie, L.
IEEE Transactions on Computers, Vol. 61, pp. 1140-1152, 2012.
A note on sorting buffers offline PDF
H.-L. Chan, N. Megow, R. Sitters, R. van Stee
Theoretical Computer Science, Vol. 423, pp. 11-18, 2012.
Universal sequencing on a single unreliable machine PDF
L. Epstein, A. Levin, N. Megow, J. Mestre, A. Marchetti-Spaccamela, M. Skutella, L Stougie
SIAM Journal on Computing, Vol. 41, pp. 565-586, 2012.
Online graph exploration: New results on old and new algorithms PDF
K. Mehlhorn, N. Megow, P. Schweitzer
Theoretical Computer Science, Vol. 463, pp. 62-72, 2012.
Special Issue on Theory and Applications of Graph Searching Problems.
2011
Online Graph Exploration: New Results on Old and New Algorithms
N. Megow, K. Mehlhorn, P. Schweitzer
In Proc. of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), LNCS 6756, pages 478-489, Springer, 2011.
Decision Support and Optimization in Shutdown and Turnaround Scheduling PDF
N. Megow, R. Möhring, J. Schulz
INFORMS J. on Computing, Vol. 23, pp. 189-204, 2011.
2010
Scheduling real-time mixed-criticality jobs
S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow, L. Stougie
In Proc. of the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), LNCS 6281, pages 90-101. Springer, 2010.
Universal sequencing on a single machine
L. Epstein, A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella, L. Stougie
In Proc. of the 14th Conference on Integer Programming and Combinatorial Optimization (IPCO 2010), LNCS 6080, pages 230-243. Springer, 2010.
Algorithms and Complexity for Periodic Real-Time Scheduling
V. Bonifaci, H.-L. Chan, A. Marchetti-Spaccamela, N. Megow
In Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pages 1350-1359, 2010.
2009
Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width
E. Günther, F. König, N. Megow
In Proc. of the 7th Workshop on Approximation and Online Algorithms (WAOA 2009), LNCS 5893, pages 170-181. Springer, 2010.
Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs
J.R. Correa, R. Raman, K. Suchan
In 8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2009), Paris, France, 2009.
Keller oder Dach zuerst.
In K. Biermann, M. Grötschel, and B. Lutz-Westphal, editors, Besser als Mathe: Moderne angewandte Mathematik aus dem Matheon zum Mit- machen, pages 111–115. Vieweg+Teubner, 2009.
2008
Coping with incomplete information in scheduling - stochastic and online models
In Operations Research Proceedings, Springer, pages 17-22, 2008.
Invited submission for winner of the Dissertation Award of the German Operations Research Society (GOR).
Optimizing the Landside Operation of a Container Terminal PDF
E. Duane, G. Froyland, T. Koch, N. Megow, H. Wren
OR Spectrum, Vol. 30, pp. 53-75, 2008.
Short note on scheduling on a single machine with one non-availability period PDF
N. Megow, Jose Verschae
2008.
2007
Coping with Incomplete Information in Scheduling - Stochastic and Online Models
N. Megow
Dissertation, Technische Universität Berlin, 2006. Cuvillier Göttingen, 2007.
2006
Approximation in Preemptive Stochastic Online Scheduling
N. Megow, T. Vredeveld
In Proc. of the 14th European Symposium on Algorithms (ESA 2006), LNCS 4168, pages 516-527, 2006.
Models and Algorithms for Stochastic Online Scheduling PDF
N. Megow, M. Uetz, T. Vredeveld
Mathematics of Operations Research, Vol. 31, pp. 513-525, 2006.
How to whack moles PDF
S. Gutiérrez, S.O. Krumke, N. Megow, T. Vredeveld
Theoretical Computer Science, Vol. 361, pp. 329-341, 2006.
2005
The Online Target Date Assignment Problem
S. Heinz, N. Megow, J. Rambau, S.O. Krumke, A. Tuchscherer, T. Vredeveld
In Proc. of the 3rd Workshop on Approximation and Online Algorithms (WAOA 2005), LNCS 3879, pages 230-243, 2006.
Stochastic Online Scheduling on Parallel Machines
N. Megow, M. Uetz, T. Vredeveld
In Proc. of the 2nd Workshop on Approximation and Online Algorithms (WAOA 2004), LNCS 3351, pages 167-180, 2005.
2004
How to Whack Moles
S.O. Krumke, N. Megow, T. Vredeveld
In Proc. of the First Workshop on Approximation and Online Algorithms (WAOA 2003), LNCS 2909, pages 192-205, 2004.
Scheduling to Minimize Average Completion Time Revisited: Deterministic On-Line Algorithms
N. Megow, A.S. Schulz
In Proc. of the First Workshop on Approximation and Online Algorithms (WAOA 2003), LNCS 2909, pages 227-234, 2004.
On-line scheduling to minimize average completion time revisited PDF
N. Megow, A.S. Schulz
Operations Research Letters, Vol. 32, pp. 485-490, 2004.
2002
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.