Megow, Nicole
Lade...
Preferred name
Megow, Nicole
Official Name
Megow, Nicole
ORCID
GND
13 Ergebnisse
Gerade angezeigt 1 - 10 von 13
- Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, An Adversarial Model for Scheduling with TestingWe introduce a novel adversarial model for scheduling with explorable uncertainty. In this model, the processing time of a job can potentially be reduced (by an a priori unknown amount) by testing the job. Testing a job j takes one unit of time and may reduce its processing time from the given upper limit ̄pj (which is the time taken to execute the job if it is not tested) to any value between 0 and ̄pj . This setting is motivated e.g., by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times on a single machine. All jobs are available from the start, but the reduction in their processing times as a result of testing is unknown, making this an online problem that is amenable to competitive analysis. The need to balance the time spent on tests and the time spent on job executions adds a novel flavor to the problem. We give the first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized online algorithms.Wissenschaftlicher ArtikelBand:82102 84 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Orienting (Hyper)graphs Under Explorable Stochastic Uncertainty(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021); ; 48 29 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Competitive Query Minimization for Stable Matching with One-Sided Uncertainty(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024); ; We study the two-sided stable matching problem with one-sided uncertainty for two sets of agents A and B, with equal cardinality. Initially, the preference lists of the agents in A are given but the preferences of the agents in B are unknown. An algorithm can make queries to reveal information about the preferences of the agents in B. We examine three query models: comparison queries, interviews, and set queries. Using competitive analysis, our aim is to design algorithms that minimize the number of queries required to solve the problem of finding a stable matching or verifying that a given matching is stable (or stable and optimal for the agents of one side). We present various upper and lower bounds on the best possible competitive ratio as well as results regarding the complexity of the offline problem of determining the optimal query set given full information.Konferenzbeitrag35 16 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Configuration Balancing for Stochastic Requests(Springer, 2023-05-22); ; ; ; The configuration balancing problem with stochastic requests generalizes well-studied resource allocation problems such as load balancing and virtual circuit routing. There are given m resources and n requests; each request has multiple possible configurations, each of which increases the load of each resource by some amount. The goal is to select one configuration for each request to minimize the makespan: the load of the most-loaded resource. In the stochastic setting, the amount by which a configuration increases the resource load is uncertain until the configuration is chosen, but we are given a probability distribution. We develop both offline and online algorithms for configuration balancing with stochastic requests. When the requests are known offline, we give a non-adaptive policy for configuration balancing with stochastic requests that O( log m / log log m)-approximates the optimal adaptive policy, which matches a known lower bound for the special case of load balancing on identical machines. When requests arrive online in a list, we give a non-adaptive policy that is O( log m ) competitive. Again, this result is asymptotically tight due to information-theoretic lower bounds for special cases (e.g., for load balancing on unrelated machines). Finally, we show how to leverage adaptivity in the special case of load balancing on related machines to obtain a constant-factor approximation offline and an O( log log m )-approximation online. A crucial technical ingredient in all of our results is a new structural characterization of the optimal adaptive policy that allows us to limit the correlations between its decisions.Wissenschaftlicher ArtikelBand:13904110 119 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Permutation Predictions for Non-Clairvoyant SchedulingIn non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a priori unknown processing requirements with the objective to minimize the total (weighted) completion time. We revisit this well-studied problem in a recently popular learning-augmented setting that integrates (untrusted) predictions in online algorithm design. While previous works used predictions on processing requirements, we propose a new prediction model, which 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 predictions have desired properties, admit a natural error measure as well as algorithms with strong performance guarantees and that they are learnable in both, theory and practice. We generalize the algorithmic framework proposed in the seminal paper by Kumar et al. (NeurIPS'18) 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 to the previously suggested single-machine algorithms.Wissenschaftlicher Artikel116 225 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Matching Augmentation via Simultaneous Contractions(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023); ; We consider the matching augmentation problem (MAP), where a matching of a graph needs to be extended into a 2-edge-connected spanning subgraph by adding the minimum number of edges to it. We present a polynomial-time algorithm with an approximation ratio of 13/8 = 1.625 improving upon an earlier 5/3-approximation. The improvement builds on a new α-approximation preserving reduction for any α ≥ 3/2 from arbitrary MAP instances to well-structured instances that do not contain certain forbidden structures like parallel edges, small separators, and contractible subgraphs. We further introduce, as key ingredients, the technique of repeated simultaneous contractions and provide improved lower bounds for instances that cannot be contracted.Konferenzbeitrag19 14 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Solution Discovery via Reconfiguration for Problems in P(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024); ; ; ; In the recently introduced framework of solution discovery via reconfiguration [Fellows et al., ECAI 2023], we are given an initial configuration of k tokens on a graph and the question is whether we can transform this configuration into a feasible solution (for some problem) via a bounded number b of small modification steps. In this work, we study solution discovery variants of polynomial-time solvable problems, namely Spanning Tree Discovery, Shortest Path Discovery, Matching Discovery, and Vertex/Edge Cut Discovery in the unrestricted token addition/removal model, the token jumping model, and the token sliding model. In the unrestricted token addition/removal model, we show that all four discovery variants remain in P. For the token jumping model we also prove containment in P, except for Vertex/Edge Cut Discovery, for which we prove NP-completeness. Finally, in the token sliding model, almost all considered problems become NP-complete, the exception being Spanning Tree Discovery, which remains polynomial-time solvable. We then study the parameterized complexity of the NP-complete problems and provide a full classification of tractability with respect to the parameters solution size (number of tokens) k and transformation budget (number of steps) b. Along the way, we observe strong connections between the solution discovery variants of our base problems and their (weighted) rainbow variants as well as their red-blue variants with cardinality constraints.Konferenzbeitrag19 37 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Online Throughput Maximization on Unrelated Machines: Commitment is No BurdenWe consider a fundamental online scheduling problem in which jobs with processing times and deadlines arrive online over time at their release dates. The task is to determine a feasible preemptive schedule on a single or multiple possibly unrelated machines that maximizes the number of jobs that complete before their deadline. Due to strong impossibility results for competitive analysis on a single machine, we require that jobs contain some slack ε > 0, which means that the feasible time window for scheduling a job is at least 1 + ε times its processing time on each eligible machine. Our contribution is two-fold: (i) We give the first non-trivial online algorithms for throughput maximization on unrelated machines, and (ii), this is the main focus of our paper, we answer the question on how to handle commitment requirements which enforce that a 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. We present an algorithm for unrelated machines that is Θ( 1ε )-competitive when the scheduler must commit upon starting a job. Somewhat surprisingly, this is the same optimal performance bound (up to constants) as for scheduling without commitment on a single machine. If commitment decisions must be made before a job’s slack becomes less than a δ-fraction of its size, we prove a competitive ratio of O( 1ε−δ ) for 0 < δ < ε. This result nicely interpolates between commitment upon starting a job and commitment upon arrival. For the latter commitment model, it is known that no (randomized) online algorithm admits any bounded competitive ratio. While we mainly focus on scheduling without migration, our results also hold when comparing against a migratory optimal solution in case of identical machines.Wissenschaftlicher ArtikelBand:19Heft:1122 207 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Santa Claus meets Makespan and Matroids: Algorithms and Reductions(Society for Industrial and Applied Mathematics, 2024-01-04); ; ; ; In this paper we study the relation of two fundamental problems in scheduling and fair allocation: makespan minimization on unrelated parallel machines and max-min fair allocation, also known as the Santa Claus problem. For both of these problems the best approximation factor is a notorious open question; more precisely, whether there is a better-than-2 approximation for the former problem and whether there is a constant approximation for the latter. While the two problems are intuitively related and history has shown that techniques can often be transferred between them, no formal reductions are known. We first show that an affirmative answer to the open question for makespan minimization implies the same for the Santa Claus problem by reducing the latter problem to the former. We also prove that for problem instances with only two input values both questions are equivalent. We then move to a special case called “restricted assignment”, which is well studied in both problems. Although our reductions do not maintain the characteristics of this special case, we give a reduction in a slight generalization, where the jobs or resources are assigned to multiple machines or players subject to a matroid constraint and in addition we have only two values. Since for the Santa Claus problem with matroids the two value case is up to constants equivalent to the general case, this draws a similar picture as before: equivalence for two values and the general case of Santa Claus can only be easier than makespan minimization. To complete the picture, we give an algorithm for our new matroid variant of the Santa Claus problem using a non-trivial extension of the local search method from restricted assignment. Thereby we unify, generalize, and improve several previous results. We believe that this matroid generalization may be of independent interest and provide several sample applications. As corollaries, we obtain a polynomial-time (2 — 1/nɛ)-approximation for two-value makespan minimization for every ɛ > 0, improving on the previous (2 — 1/m)-approximation, and a polynomial-time (1.75 + ɛ)- approximation for makespan minimization in the restricted assignment case with two values, improving the previous best rate of .Wissenschaftlicher Artikel138 311 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Protecting the Connectivity of a Graph Under Non-Uniform Edge Failures(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025); ; ; Zhang, GuochuanWe 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.Konferenzbeitrag10 21