Littérature scientifique sur le sujet « Explorable uncertainty »

In a wide range of recommendation systems, self-interested individuals (“agents”) make decisions over time, using information revealed by other agents in the past, and producing information that may help agents in the future. Each agent would like to exploit the best action given the current information but would prefer the previous agents to explore various alternatives to collect information. A social planner, by means of a well-designed recommendation policy, can incentivize the agents to balance exploration and exploitation in order to maximize social welfare or some other objective. The recommendation policy can be modeled as a multiarmed bandit algorithm under Bayesian incentivecompatibility (BIC) constraints. This line of work has received considerable attention in the “economics and computation” community. Although in prior work, the planner interacts with a single agent at a time, the present paper allows the agents to affect one another directly in a shared environment. The agents now face two sources of uncertainty: what is the environment, and what would the other agents do? We focus on “explorable” actions: those that can be recommended by some BIC policy. We show how the principal can identify and explore all such actions.

AbstractThis article studies the Minimum Spanning Tree Problem under Explorable Uncertainty as well as a related vertex uncertainty version of the problem. We particularly consider special instance types, including cactus graphs, for which we provide randomized algorithms. We introduce the problem of finding a minimum weight spanning star under uncertainty for which we show that no algorithm can achieve constant competitive ratio.

AbstractIn computing with explorable uncertainty, one considers problems where the values of some input elements are uncertain, typically represented as intervals, but can be obtained using queries. Previous work has considered query minimization in the settings where queries are asked sequentially (adaptive model) or all at once (non-adaptive model). We introduce a new model where k queries can be made in parallel in each round, and the goal is to minimize the number of query rounds. Using competitive analysis, we present upper and lower bounds on the number of query rounds required by any algorithm in comparison with the optimal number of query rounds for the given instance. Given a set of uncertain elements and a family of m subsets of that set, we study the problems of sorting all m subsets and of determining the minimum value (or the minimum element(s)) of each subset. We also study the selection problem, i.e., the problem of determining the i-th smallest value and identifying all elements with that value in a given set of uncertain elements. Our results include 2-round-competitive algorithms for sorting and selection and an algorithm for the minimum value problem that uses at most $$(2+\varepsilon ) \cdot \mathrm {opt}_k+\mathrm {O}\left( \frac{1}{\varepsilon } \cdot \lg m\right) $$ ( 2 + ε ) · opt k + O 1 ε · lg m query rounds for every $$0<\varepsilon <1$$ 0 < ε < 1 , where $$\mathrm {opt}_k$$ opt k is the optimal number of query rounds.

In the context of decision making under explorable uncertainty, scheduling with testing is a powerful technique used in the management of computer systems to improve performance via better job-dispatching decisions. Upon job arrival, a scheduler may run some testing algorithm against the job to extract some information about its structure, e.g., its size, and properly classify it. The acquisition of such knowledge comes with a cost because the testing algorithm delays the dispatching decisions, though this is under control. In this paper, we analyze the impact of such extra cost in a load balancing setting by investigating the following questions: does it really pay off to test jobs? If so, under which conditions? Under mild assumptions connecting the information extracted by the testing algorithm in relationship with its running time, we show that whether scheduling with testing brings a performance degradation or improvement strongly depends on the traffic conditions, system size and the coefficient of variation of job sizes. Thus, the general answer to the above questions is non-trivial and some care should be considered when deploying a testing policy. Our results are achieved by proposing a load balancing model for scheduling with testing that we analyze in two limiting regimes. When the number of servers grows to infinity in proportion to the network demand, we show that job-size testing actually degrades performance unless short jobs can be predicted reliably almost instantaneously and the network load is sufficiently high. When the coefficient of variation of job sizes grows to infinity, we construct testing policies inducing an arbitrarily large performance gain with respect to running jobs untested.

Les plateformes de calcul haute performance (HPC) sont la solution idéale pour exécuter des applications exigeantes en termes de calcul. Étant donné leur consommation importante en énergie, le besoin d'algorithmes plus efficaces en termes d'énergie est indispensable. De meilleurs algorithmes d'ordonnancement peuvent être conçus en exploitant les caractéristiques essentielles d'une plateforme HPC, telles que sa topologie de réseau et l'hétérogénéité de ses machines. On peut également obtenir de meilleures performances en concevant des modèles plus réalistes, qui saisissent les fonctionnalités d'applications réelles. Ainsi, permettre aux algorithmes d’ordonnancement de décider de la quantité de ressources allouées à une application, ou de la vitesse d'exécution des machines, peut ouvrir la voie à de nouvelles implémentations compatibles avec la plateforme. Dans la première partie de la thèse, nous introduisons un modèle qui prend en compte à la fois la topologie et l'hétérogénéité d'une plateforme en introduisant deux types de machines. Nous augmentons le problème d'ordonnancement avec des contraintes dont le but est de réduire implicitement le mouvement des données pendant l'exécution des tâches sur des machines parallèles, et lors de la communication avec le système de fichiers. Nous proposons des algorithmes qui ordonnancent les tâches au cours du temps, et décident du nombre de ressources allouées à une tâche, en tenant compte de ces contraintes supplémentaires. Dans la deuxième partie de la thèse, on s'intéresse à l'incertitude liée à la charge de travail d'une application, cette charge étant directement liée au temps nécessaire à son exécution. La plupart des travaux de la littérature considèrent cette valeur connue à l'avance. C'est cependant rarement le cas dans les systèmes réels. Dans notre approche, la charge de travail donnée est une charge possible mais qui peut éventuellement être réduite. On introduit alors des tests spécifiques à l'application qui peuvent réduire la charge de travail d'une tâche. Étant donné que le test (par exemple, la compression) doit également être exécuté, et que la quantité de réduction (par exemple, la taille) est inconnue avant la fin du test, la décision d'exécuter ou non le test pour une tâche doit être prise. On propose des algorithmes compétitifs pour le problème d'ordonnancement de telles tâches, dans le but de minimiser l'énergie consommée par un ensemble de machines pour lesquelles on peut modifier la vitesse. Dans la troisième partie de la thèse, nous nous intéressons à un contexte similaire d'entrées incertaines et nous considérons un modèle dans lequel les temps d’exécution des tâches ne sont pas connus à l'avance. Nous augmentons l'entrée du problème en introduisant des valeurs prédites des temps d'exécution.Nous concevons alors des algorithmes qui ont d'excellentes performances lorsque les prédictions sont exactes, tout en restant compétitifs lorsque les prédictions se révèlent inexactes
High performance computers (HPCs) is the go-to solution for running computationally demanding applications. As the limit of energy consumption is already achieved, the need for more energy efficient algorithms is critical.Taking advantage of the core characteristics of an HPC, such as its network topology and the heterogeneity of the machines, could lead to better scheduling algorithms. In addition, designing more realistic models, that grasp the features of real-life applications, is a work in the same direction of achieving better performance. Allowing scheduling algorithms to decide either the amount of resources allocated to an application or the running speed of the resources can pave the path to new platform-aware implementations. In the first part of the thesis, we introduce a model which takes into account both the topology and the heterogeneity of a platform by introducing two kind of machines. We augment the scheduling problem with constraints whose purpose is to implicitly reduce data movement either during parallel execution or during the communication with the file system. We propose algorithms that can decide the number of resources allocated to an application taking into consideration the extra constraints.In the second part of the thesis, we deal with the uncertainty on part of the input and more specifically, the workload of an application, that is strictly related to the time needed for its completion. Most works in the literature consider this value known in advance. However, this is rarely the case in real-life systems.In our approach, the given workload is a worst case scenario for the execution of an application. We introduce application-specific tests that may decrease the workload of a task.Since the test (e.g. compression) takes some time, and since the amount of reduction (e.g. in size) is unknown before the completion of the test, the decision of running the test for a task or not has to be taken. We propose competitive algorithms for the problem of scheduling such tasks, in order to minimize the energy consumed in a set of speed-adjustable machines. In the third part of the thesis, we focus on a similar setting of uncertain input and we consider a model where the processing times are not known in advance. Here, we augment the input of the problem by introducing predicted values in place of the unknown processing times. We design algorithms that perform optimally when the predictions are accurate while remaining competitive to the best known ones otherwise

AbstractDecision-making under uncertainty is a major challenge in logistics. Mathematical optimization has a long tradition in providing powerful methods for solving logistics problems. While classical optimization models for uncertainty in the input data do not consider the option to actively query the precise value of uncertain input elements, this option is in practice often available at a certain cost. The recent line of research on optimization under explorable uncertainty develops methods with provable performance guarantees for such scenarios. In this chapter, we highlight some recent results from the mathematical optimization perspective and outline the potential power of such model and techniques for solving logistics problems.

AbstractThe problem of scheduling with testing in the framework of explorable uncertainty models environments where some preliminary action can influence the duration of a task. In the model, each job has an unknown processing time that can be revealed by running a test. Alternatively, jobs may be run untested for the duration of a given upper limit. Recently, Dürr et al. [4] have studied the setting where all testing times are of unit size and have given lower and upper bounds for the objectives of minimizing the sum of completion times and the makespan on a single machine. In this paper, we extend the problem to non-uniform testing times and present the first competitive algorithms. The general setting is motivated for example by online user surveys for market prediction or querying centralized databases in distributed computing. Introducing general testing times gives the problem a new flavor and requires updated methods with new techniques in the analysis. We present constant competitive ratios for the objective of minimizing the sum of completion times in the deterministic case, both in the non-preemptive and preemptive setting. For the preemptive setting, we additionally give a first lower bound. We also present a randomized algorithm with improved competitive ratio. Furthermore, we give tight competitive ratios for the objective of minimizing the makespan, both in the deterministic and the randomized setting.

Learning-augmented algorithms have been attracting increasing interest, but have only recently been considered in the setting of explorable uncertainty where precise values of uncertain input elements can be obtained by a query and the goal is to minimize the number of queries needed to solve a problem. We study learning-augmented algorithms for sorting and hypergraph orientation under uncertainty, assuming access to untrusted predictions for the uncertain values. Our algorithms provide improved performance guarantees for accurate predictions while maintaining worst-case guarantees that are best possible without predictions. For sorting, our algorithm uses the optimal number of queries for accurate predictions and at most twice the optimal number for arbitrarily wrong predictions. For hypergraph orientation, for any γ≥2, we give an algorithm that uses at most 1+1/γ times the optimal number of queries for accurate predictions and at most γ times the optimal number for arbitrarily wrong predictions. These tradeoffs are the best possible. We also consider different error metrics and show that the performance of our algorithms degrades smoothly with the prediction error in all the cases where this is possible.

In this article, we adopt the paradigm of scheduling under explorable uncertainty to explore test-taking strategies to solve standardized tests in terms of maximizing the correct questions answered. From this approach, a test taker considers a number of questions and has the possibility to read in order to obtain the difficulty of the question. Later, he/she has the option, for example, to answer the question or to skip the one that seemed difficult and read the next question in the test. Specifically, we state the problem definition by considering two test-taking strategies, formulate and implement a mathematical model, and generate computational experiments in order to determine the dominance of one strategy over another. The results show that the dominance depends directly on the design of the test and the maximum time to perform it, so knowing these parameters allow us to provide algorithmic insights to address this problem.