Online Algorithms

Online optimization deals with problems, where parts of the input are initially unknown. A prominent subcategory are problems, where parts of the input arrive over time and irrovocable decisions have to be made without knowledge of the future. For example, consider a scheduling problem where the jobs arrive over time and we have to decide immediately upon the arrival of a job on which machine we want to schedule it. We design and analyse algorithms for online problems in a worst-case setting, where we assume that an adversary fixes the still unknown input in a worst-case manner.

As another example consider online throughput maximization with commitment requirements. In online throughput maximization, jobs with release dates and deadlines arive online over time and the task is to maximize the number of jobs that finish within their deadline. Commitment requirements enforce that the scheduler has to guarantee at a certain point in time the completion of admitted jobs. This is very relevant, e.g., in providing cloud-computing services and disallows last-minute rejections of critical tasks. As part of the project, we designed an algorithm for optimally handling commitment in online throughput maximization.

Chalkboard with inscription "What's Next"

Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty arxiv.org
Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schlöter
ESA 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
Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, Jens Schlöter
AAAI 2022

Double Coverage with Machine-Learned Advice arxiv.org
Alexander Lindermayr, Nicole Megow, Bertrand Simon
ITCS 2022

Explorable Uncertainty Meets Decision-Making in Logistics springer.com
Nicole Megow and Jens Schlöter
Dynamics in Logistics: 35-56, 2021 springer.com

Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty pdf
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow, Jens Schlöter
Accepted for publication at ESA 2021

Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments
Jacob Focke, Nicole Megow, Julie Meißner
ACM Journal of Experimental Algorithmics 25(1), Article 1.14, 2020

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.

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

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

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

Updated by: Lukas Barning

RSS

Print page

Online Algorithms

Publications on Online Algorithms