Eberle, Franziska
Lade...
4 Ergebnisse
Gerade angezeigt 1 - 4 von 4
- 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 118 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Scheduling and Packing Under Uncertainty(2020-11-13); ; ; Incomplete information is a major challenge when translating combinatorial optimization results to recommendations for real-world applications since problem relevant parameters change frequently or are not known in advance. A particular solution may perform well on some specific input data or estimation thereof, but once the data is slightly perturbed or new tasks need to be performed, the solution may become arbitrarily bad or even infeasible. Thus, either solving the problem under uncertainty or efficiently updating the solution becomes a necessity. This thesis explores several models for uncertainty in various problems from two fundamental fields of combinatorial optimization: scheduling and packing. Scheduling arise whenever scarce resources have to complete a set of tasks while optimizing some objective such as minimizing the duration of the system or maximizing the throughput in a given time interval. Packing problems appear whenever items have to be assigned to resources with capacities. Typically, they require compliance with certain capacity constraints while maximizing the overall value of successfully packed items. Incomplete information may be caused by various reasons, such as the unpredictable arrival of new tasks or items or having only estimates of input parameters at hand. In any of these cases, we are interested in finding provably good solutions in reasonable time. In other words, we would like to design algorithms that deal with incomplete information while performing sufficiently well. This thesis focuses on three models of uncertainty in the input: stochastic, online, and dynamic.Dissertation530 473 - 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 206 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Fully Dynamic Algorithms for Knapsack Problems with Polylogarithmic Update Time(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021); ; ; ; Wiese, AndreasKnapsack problems are among the most fundamental problems in optimization. In the Multiple Knapsack problem, we are given multiple knapsacks with different capacities and items with values and sizes. The task is to find a subset of items of maximum total value that can be packed into the knapsacks without exceeding the capacities. We investigate this problem and special cases thereof in the context of dynamic algorithms and design data structures that efficiently maintain near-optimal knapsack solutions for dynamically changing input. More precisely, we handle the arrival and departure of individual items or knapsacks during the execution of the algorithm with worst-case update time polylogarithmic in the number of items. As the optimal and any approximate solution may change drastically, we maintain implicit solutions and support polylogarithmic time query operations that can return the computed solution value and the packing of any given item. While dynamic algorithms are well-studied in the context of graph problems, there is hardly any work on packing problems (and generally much less on non-graph problems). Motivated by the theoretical interest in knapsack problems and their practical relevance, our work bridges this gap.Konferenzbeitrag13 28