Skip to main content

Publications

2020

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments.
Jacob Focke, Nicole Megow, Julie Meißner.
Accepted for publication at ACM Journal of Experimental Algorithmics.

Computing a Minimum-Cost k-hop Steiner Tree in Tree-Like Metrics  PDF
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
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
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.

Online Metric Algorithms with Untrusted Predictions.  arxiv.org  code on github
Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak and Bertrand Simon.
ICML Conference abs/2003.02144 , 2020 - ICML 2020: 345-355

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

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.
IPDPS 1061-1070, 2020

Scheduling on Hybrid Platforms: Improved Approximability Window.  arxiv.org
Vincent Fagnon, Imed Kacem, Giorgio Lucarelli and Bertrand Simon.
LATIN Symposium, 2020 - LATIN 2020: 38-49

Scheduling on Two Types of Resources: a Survey  arxiv.org
Olivier Beaumont, Louis-Claude Canon, Lionel Eyraud-Dubois, Giorgio Lucarelli, Loris Marchal, Clément Mommessin, Bertrand Simon and Denis Trystram.
ACM Computing Surveys 53(3): 56:1-56:36, 2020

Energy Minimization in DAG Scheduling on MPSoCs at Run-Time: Theory and Practice  PDF  daghstuhl.de
Bertrand Simon, Joachim Falk, Nicole Megow and Jürgen Teich.
NG-RES Workshop 2:1-2:13, 2020.

A PTAS for Euclidean TSP with Hyperplane Neighborhoods. arxiv.org
A. Antoniadis, K. Fleszar, R. Hoeksma, and K. Schewior.
ACM Trans. Algorithms 16(3): 38:1-38:16, 2020

2019

On the complexity of Anchored Rectangle Packing  dagstuhl.de
A. Antoniadis, F. Biermeier, A. Cristi, C. Damerius, R. Hoeksma, D. Kaaser, P. Kling, and L. Nölke.
27th European Symposium on Algorithms (ESA) 8:1-8:14, 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 PDF  daghstuhl.de
J.J. Chen, R. Hoeksma, T. Hahn, N. Megow, G. von der Brueggen
Proc. 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  sciencedirect.com
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).

Limiting the Memory Footprint when Dynamically Scheduling DAGs on Shared-Memory Platforms  sciencedirect.com
Loris Marchal, Bertrand Simon, Frédéric Vivien.
JPDC journal 128: 30-42, 2019

Network Congestion Games are Robust to Variable Demand  ernet.in
J. Correa, R. Hoeksma, and M. Schröder.
Presented at: The 13th Conference on Web and Internet Economics 397, WINE 2017 Conference proceedings only contained and extended abstract.

The price of anarchy for utilitarian scheduling games on related machines.  PDF sciencedirect.com
R. Hoeksma and M. Uetz.
Discrete Optimization 31: 29-39, 2019
Download BIB-File

2018

SUPERSET: A (super)natural variant of the card game SET  dagstuhl.de
F. Botler, A. Cristi, R. Hoeksma, K. Schewior, and A. Tönnis.
9th International Conference on Fun with Algorithms 12:1-12:17, FUN 2018
Download BIB-File

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.

Online Scheduling of Sequential Task Graphs on Hybrid Platforms.   springer.com  inria.fr
Louis-Claude Canon, Loris Marchal, Bertrand Simon and Frédéric Vivien.
Euro-Par Conference, 2018.

Parallel Scheduling of DAGs under Memory Constraints  PDF  ieeexplore.ieee.org
Loris Marchal, Hanna Nagy, Bertrand Simon and Frédéric Vivien.
IPDPS Symposium 204-213, 2018

Malleable task-graph scheduling with a practical speed-up model.  PDF
Loris Marchal, Bertrand Simon, Oliver Sinnen, Frédéric Vivien
IEEE Trans. Parallel Distrib. Syst. 29(6): 1357-1370, 2018

Approximation Algorithms for Connected Graph Factors of Minimum Weight. PDF
K. Cornelissen, R. Hoeksma, B. Manthey, N.S. Narayanaswamy, C.S. Rahul, and M. Waanders.
Theory of Computing Systems, 62(2):441—464, 2018.
external PDF-File on springer.com

2017

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments  PDF  daghstuhl.de
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  springer.com
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  siam.org
J. Meißner, N. Megow, M. Skutella
SIAM Journal on Computing 46(4): 1217-1240, 2017.

Packing a Knapsack of Unknown Capacity  PDF  siam.org
Y. Disser, M. Klimm, N. Megow, S. Stiller
SIAM Journal on Discrete Mathematics 31(3): 1477-1497, 2017.

Network Congestion Games are Robust to Variable Demand  ernet.in
J. Correa, R. Hoeksma, and M. Schröder.
Presented at: The 13th Conference on Web and Internet Economics (WINE 2017). Conference proceedings only contained and extended abstract.

Posted price mechanisms for a random stream of customers.  PDF   PDF
J. Correa, P. Foncea, R. Hoeksma, T. Oosterwijk, and T. Vredeveld.
The 2017 ACM conference on Economics and Computation (EC ’17).
Download BIB-File

2016

The Power of Migration in Online Machine Minimization  PDF  acm.org
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  siam.org
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 PDF  acm.org
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  siam.org
N. Megow, M. Skutella, J. Verschae, A. Wiese
SIAM Journal on Computing. 45-3, pp. 859-880, 2016

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. Newog, 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.