Nicole Megow
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Nicole Megow has a total of 141 co-authors. Here are the top co-authors by number of shared publications:
- Lin Chen
Zhejiang University
11 shared publications - Franziska Eberle
London School of Economics and Political Science
9 shared publications Alberto Marchetti-Spaccamela
6 shared publications- Lukas Nölke
Faculty of Mathematics and Computer Science, University of Bremen, Bremen, Germany
6 shared publications - Kevin Schewior
Department of Mathematics and Computer Science University of Cologne Germany
5 shared publications Leen Stougie
5 shared publications
Latest Publications
- 23 July 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1141-1167
Protecting the Connectivity of a Graph Under Nonuniform Edge Failures
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a nonuniform failure model. We introduce the [Formula: see text]-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains [Formula: see text]-edge-connectivity between given terminal pairs against edge failures, assuming at most [Formula: see text] unprotected edges can fail. We design polynomial-time exact algorithms for the cases where [Formula: see text] and [Formula: see text] are small and approximation algorithms for general values of [Formula: see text] and [Formula: see text]. Additionally, we show that when both [Formula: see text] and [Formula: see text] are part of the input, even deciding whether a given solution is feasible is [Formula: see text]-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either [Formula: see text] or [Formula: see text] is constant, for which our new hardness result now provides justification.
- 23 July 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 40 (3) , 1141-1167
Protecting the Connectivity of a Graph Under Nonuniform Edge Failures
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a nonuniform failure model. We introduce the [Formula: see text]-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains [Formula: see text]-edge-connectivity between given terminal pairs against edge failures, assuming at most [Formula: see text] unprotected edges can fail. We design polynomial-time exact algorithms for the cases where [Formula: see text] and [Formula: see text] are small and approximation algorithms for general values of [Formula: see text] and [Formula: see text]. Additionally, we show that when both [Formula: see text] and [Formula: see text] are part of the input, even deciding whether a given solution is feasible is [Formula: see text]-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either [Formula: see text] or [Formula: see text] is constant, for which our new hardness result now provides justification.
- Open Access
- 22 June 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-30
Recoverable robust optimization with commitment
We propose a model for recoverable robust optimization with commitment . Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust solution that, after the failing elements are revealed, can be augmented in a limited way. However, we commit to preserve the non-failing elements of the initial solution. We settle the computational complexity of such a robust counterpart of various classical polynomial-time solvable combinatorial optimization problems. We show, for the weighted matroid independent set problem, that an optimal solution to the nominal problem is also optimal for its robust counterpart. Indeed, matroids are provably the only structures with this strong property. Robust counterparts of other problems are -hard such as the matching problem and the stable set problem, even in bipartite graphs. However, we establish polynomial-time algorithms for the robust counterparts of the unweighted stable set problem in bipartite graphs and the weighted stable set problem in interval graphs, also known as the interval scheduling problem.
- 22 June 2026
- Published by Springer Nature in Mathematical Programming
- p. 1-30
Open AccessRecoverable robust optimization with commitment
We propose a model for recoverable robust optimization with commitment . Given a combinatorial optimization problem and uncertainty about elements that may fail, we ask for a robust solution that, after the failing elements are revealed, can be augmented in a limited way. However, we commit to preserve the non-failing elements of the initial solution. We settle the computational complexity of such a robust counterpart of various classical polynomial-time solvable combinatorial optimization problems. We show, for the weighted matroid independent set problem, that an optimal solution to the nominal problem is also optimal for its robust counterpart. Indeed, matroids are provably the only structures with this strong property. Robust counterparts of other problems are -hard such as the matching problem and the stable set problem, even in bipartite graphs. However, we establish polynomial-time algorithms for the robust counterparts of the unweighted stable set problem in bipartite graphs and the weighted stable set problem in interval graphs, also known as the interval scheduling problem.
- 13 June 2026
- Published by Springer Nature
- p. 265-281
Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
- 13 June 2026
- Published by Springer Nature
- p. 265-281
Polytope Scheduling with Groups: Unified Models and Optimal Guarantees
- 2 March 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 55 (2) , 247-279
The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling
The polytope scheduling problem (PSP) was introduced by Im, Kulkarni, and Munagala [J. ACM, 65 (2018), pp. 3:1–3:33] as a very general abstraction of resource allocation over time, where ...
- 2 March 2026
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 55 (2) , 247-279
The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling
The polytope scheduling problem (PSP) was introduced by Im, Kulkarni, and Munagala [J. ACM, 65 (2018), pp. 3:1–3:33] as a very general abstraction of resource allocation over time, where ...
- 17 July 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 221-254
Fast Combinatorial Algorithms for Efficient Sortation
- 17 July 2025
- Published by Springer Nature in Mathematical Programming
- Vol. 216 (1-2) , 221-254
Fast Combinatorial Algorithms for Efficient Sortation
- Open Access
- 10 July 2025
- Published by Springer Nature in Algorithmica
- p. 1-41
Boosting Double Coverage for k-Server via Imperfect Predictions
We study the online k -server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence, we assume that there is given some advice (for example, machine-learned predictions) on an algorithm’s decision. There is, however, no guarantee on the quality of the prediction, and it might be far from being correct. Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for k -server on the line (Chrobak et al. in SIAM J Discret Math 4(2):172–181, 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent worst-case performance guarantee, which is a function of a user-defined confidence parameter, and which interpolates smoothly between an optimal performance in case that all predictions are correct, and the best-possible performance regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any k almost optimal guarantees, within a class of deterministic learning-augmented algorithms respecting local and memoryless properties. Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is noteworthy that the previous algorithm crucially exploits memory, whereas our algorithm is memoryless. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.
- 10 July 2025
- Published by Springer Nature in Algorithmica
- p. 1-41
Open AccessBoosting Double Coverage for k-Server via Imperfect Predictions
We study the online k -server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence, we assume that there is given some advice (for example, machine-learned predictions) on an algorithm’s decision. There is, however, no guarantee on the quality of the prediction, and it might be far from being correct. Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for k -server on the line (Chrobak et al. in SIAM J Discret Math 4(2):172–181, 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent worst-case performance guarantee, which is a function of a user-defined confidence parameter, and which interpolates smoothly between an optimal performance in case that all predictions are correct, and the best-possible performance regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any k almost optimal guarantees, within a class of deterministic learning-augmented algorithms respecting local and memoryless properties. Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is noteworthy that the previous algorithm crucially exploits memory, whereas our algorithm is memoryless. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.
- Open Access
- 13 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 12 (2) , 1-26
Permutation Predictions for Non-Clairvoyant Scheduling
In non-clairvoyant scheduling, the task is to schedule jobs with a priori unknown processing requirements. We revisit this well-studied problem with the objective of minimizing the total (weighted) completion time in a recently popular learning-augmented setting that integrates possibly imperfect predictions into online algorithm design. While previous works used predictions on processing requirements, we propose a new prediction model that provides a relative order of jobs, which could be seen as predicting algorithmic actions rather than parts of the unknown input. We show that these succinct predictions have desired properties, admit a natural error measure, and enable algorithms with strong performance guarantees. Additionally, these predictions are learnable in both theory and practice. We generalize the algorithmic framework proposed in the seminal article by Purohit, Kumar, and Svitkina (NeurIPS 2018) and present the first learning-augmented scheduling results for weighted jobs and unrelated machines. We demonstrate in empirical experiments the practicability and superior performance compared with the previously suggested single-machine algorithms.
- 13 May 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Parallel Computing
- Vol. 12 (2) , 1-26
Open AccessPermutation Predictions for Non-Clairvoyant Scheduling
In non-clairvoyant scheduling, the task is to schedule jobs with a priori unknown processing requirements. We revisit this well-studied problem with the objective of minimizing the total (weighted) completion time in a recently popular learning-augmented setting that integrates possibly imperfect predictions into online algorithm design. While previous works used predictions on processing requirements, we propose a new prediction model that provides a relative order of jobs, which could be seen as predicting algorithmic actions rather than parts of the unknown input. We show that these succinct predictions have desired properties, admit a natural error measure, and enable algorithms with strong performance guarantees. Additionally, these predictions are learnable in both theory and practice. We generalize the algorithmic framework proposed in the seminal article by Purohit, Kumar, and Svitkina (NeurIPS 2018) and present the first learning-augmented scheduling results for weighted jobs and unrelated machines. We demonstrate in empirical experiments the practicability and superior performance compared with the previously suggested single-machine algorithms.
- Open Access
- 1 March 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (6) , 813-841
Online Metric Matching on the Line with Recourse
In online metric matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all located on the real line. The goal is to minimize the sum of distances between the requests and their assigned servers. The best known online algorithm achieves a competitive ratio of $$\Theta (\log n)$$ , leaving a gap to the best-known lower bound of $$\Omega (\sqrt{\log n})$$ . In this work, we approach the problem in a recourse model where online decisions can be partially revised, allowing for the reassignment of previously matched edges. In contrast to the traditional online setting, we show that with an amortized recourse budget of $$O(\log n)$$ , we can obtain an O(1)-competitive algorithm for online metric matching on the line. This is one of the first non-trivial results for metric matching with recourse. Additionally, for so-called alternating instances, where no more than one request lies between two servers, we achieve a near-optimal result. Specifically, we give a simple algorithm that is $$(1+\varepsilon )$$ -competitive and reassigns any request at most $$O(\frac{1}{\varepsilon ^2})$$ times. This special case is particularly noteworthy, as a lower bound of $$\Omega (\log n)$$ , constructed using such instances, applies to a broad class of online algorithms, including all deterministic algorithms studied in the literature.- 1 March 2025
- Published by Springer Nature in Algorithmica
- Vol. 87 (6) , 813-841
Open AccessOnline Metric Matching on the Line with Recourse
In online metric matching on the line, n requests appear one by one and have to be matched immediately and irrevocably to a given set of servers, all located on the real line. The goal is to minimize the sum of distances between the requests and their assigned servers. The best known online algorithm achieves a competitive ratio of $$\Theta (\log n)$$ , leaving a gap to the best-known lower bound of $$\Omega (\sqrt{\log n})$$ . In this work, we approach the problem in a recourse model where online decisions can be partially revised, allowing for the reassignment of previously matched edges. In contrast to the traditional online setting, we show that with an amortized recourse budget of $$O(\log n)$$ , we can obtain an O(1)-competitive algorithm for online metric matching on the line. This is one of the first non-trivial results for metric matching with recourse. Additionally, for so-called alternating instances, where no more than one request lies between two servers, we achieve a near-optimal result. Specifically, we give a simple algorithm that is $$(1+\varepsilon )$$ -competitive and reassigns any request at most $$O(\frac{1}{\varepsilon ^2})$$ times. This special case is particularly noteworthy, as a lower bound of $$\Omega (\log n)$$ , constructed using such instances, applies to a broad class of online algorithms, including all deterministic algorithms studied in the literature. - Open Access
Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the $(p,q)$-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains $p$-edge-connectivity between given terminal pairs against edge failures, assuming at most $q$ unprotected edges can fail. We design polynomial-time exact algorithms for the cases where $p$ and $q$ are small and approximation algorithms for general values of $p$ and $q$. Additionally, we show that when both $p$ and $q$ are part of the input, even deciding whether a given solution is feasible is NP-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either $p$ or $q$ is constant, for which our new hardness result now provides justification.Open AccessProtecting the Connectivity of a Graph Under Non-Uniform Edge Failures
We study the problem of guaranteeing the connectivity of a given graph by protecting or strengthening edges. Herein, a protected edge is assumed to be robust and will not fail, which features a non-uniform failure model. We introduce the $(p,q)$-Steiner-Connectivity Preservation problem where we protect a minimum-cost set of edges such that the underlying graph maintains $p$-edge-connectivity between given terminal pairs against edge failures, assuming at most $q$ unprotected edges can fail. We design polynomial-time exact algorithms for the cases where $p$ and $q$ are small and approximation algorithms for general values of $p$ and $q$. Additionally, we show that when both $p$ and $q$ are part of the input, even deciding whether a given solution is feasible is NP-complete. This hardness also carries over to Flexible Network Design, a research direction that has gained significant attention. In particular, previous work focuses on problem settings where either $p$ or $q$ is constant, for which our new hardness result now provides justification. - Open Access
- 6 November 2024
- Published by Association for Computing Machinery (ACM)
- p. 197-206
The Safe and Effective Use of Optimistic Period Predictions
- 6 November 2024
- Published by Association for Computing Machinery (ACM)
- p. 197-206
Open AccessThe Safe and Effective Use of Optimistic Period Predictions