Schlöter, Jens
Lade...
5 Ergebnisse
Gerade angezeigt 1 - 5 von 5
- 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.Konferenzbeitrag32 16 - 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 28 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Optimization under explorable uncertainty: beyond the worst-case(2023-11-10); ; ; When solving optimization problems that arise in real-world applications, uncertainty in the input data and incomplete information are major challenges. Consider for example varying transportation times depending on traffic conditions or weather, variable parameters such as bandwidth and demands, or decentralized data that is updated infrequently. The three major mathematical models for uncertainty in optimization problems are online optimization, stochastic optimization and robust optimization. These models have in common that the uncertain information is usually either revealed passively over time or not at all. Optimization algorithms for problems in these models have to cope with this type of uncertainty and make decisions based on incomplete information. In particular, they do not have the option, not even at a cost, to actively obtain new information that helps to handle the optimization task at hand. This thesis considers the model of explorable uncertainty, where uncertain parts in the input of an optimization problem can be queried at a certain cost to reveal more information. The goal in explorable uncertainty is to design algorithms that query uncertain parameters until the revealed information is sufficient to determine an optimal solution to the underlying optimization problem, with the objective to minimize the query cost. So far, explorable uncertainty has mostly been studied in the adversarial setting, where we assume that query results are returned in a worst-case manner and analyze algorithms in terms of their competitive ratio. This setting however leads to strong lower bounds on the competitive ratio for several interesting problems and might be too pessimistic in many real world applications. Instead, this thesis considers several problems under explorable uncertainty and analyzes them in settings that go beyond the worst-case. In particular, we study a learning-augmented and a stochastic setting for problems under explorable uncertainty.Dissertation319 499 - 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 309 - Some of the metrics are blocked by yourconsent settings
Item-typ:Veröffentlichung, Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022); ; We study how to utilize (possibly erroneous) predictions in a model for computing under uncertainty in which an algorithm can query unknown data. Our aim is to minimize the number of queries needed to solve the minimum spanning tree problem, a fundamental combinatorial optimization problem that has been central also to the research area of explorable uncertainty. For all integral γ ≥ 2, we present algorithms that are γ-robust and (1+1/γ)-consistent, meaning that they use at most γOPT queries if the predictions are arbitrarily wrong and at most (1+1/γ)OPT queries if the predictions are correct, where OPT is the optimal number of queries for the given instance. Moreover, we show that this trade-off is best possible. Furthermore, we argue that a suitably defined hop distance is a useful measure for the amount of prediction error and design algorithms with performance guarantees that degrade smoothly with the hop distance. We also show that the predictions are PAC-learnable in our model. Our results demonstrate that untrusted predictions can circumvent the known lower bound of 2, without any degradation of the worst-case ratio. To obtain our results, we provide new structural insights for the minimum spanning tree problem that might be useful in the context of query-based algorithms regardless of predictions. In particular, we generalize the concept of witness sets - the key to lower-bounding the optimum - by proposing novel global witness set structures and completely new ways of adaptively using those.Konferenzbeitrag20 21