NMNicole Megow

Nicole Megow

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Protecting the Connectivity of a Graph Under Nonuniform Edge Failures

    by Felix Hommelsheim, Zhenwei Liu, Nicole Megow, Guochuan Zhang

    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

    Recoverable robust optimization with commitment

    by Felix Hommelsheim, Nicole Megow, Komal Muluk, Britta Peis

    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.

  • The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling

    by Sven Jäger, Alexander Lindermayr, Nicole Megow

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

  • Fast Combinatorial Algorithms for Efficient Sortation

    by Madison Van Dyk, Kim Klause, Jochen Koenemann, Nicole Megow


  • Open Access

    Boosting Double Coverage for k-Server via Imperfect Predictions

    by Alexander Lindermayr, Nicole Megow, Bertrand Simon

    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

    Permutation Predictions for Non-Clairvoyant Scheduling

    by Alexander Lindermayr, Nicole Megow

    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

    Online Metric Matching on the Line with Recourse

    by Nicole Megow, Lukas Nölke

    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)$$ Θ ( log n ) , leaving a gap to the best-known lower bound of $$\Omega (\sqrt{\log n})$$ Ω ( 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)$$ 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 )$$ ( 1 + ε ) -competitive and reassigns any request at most $$O(\frac{1}{\varepsilon ^2})$$ O ( 1 ε 2 ) times. This special case is particularly noteworthy, as a lower bound of $$\Omega (\log n)$$ Ω ( 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

    by Felix Hommelsheim, Zhenwei Liu, Nicole Megow, Guochuan Zhang

    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

    The Safe and Effective Use of Optimistic Period Predictions

    by Sanjoy Baruah, Pontus Ekberg, Alexander Lindermayr, Alberto Marchetti-Spaccamela, Nicole Megow, Leen Stougie