1,721,095 research outputs found
Parameterized Analysis of Paging and List Update Algorithms
No full textIt is well-established that input sequences for paging and list update have locality of reference. In this paper we analyze the performance of algorithms for these problems in terms of the amount of locality in the input sequence. We define a measure for locality that is based on Denning's working set model and express the performance of well known algorithms in term of this parameter. This introduces parameterizedstyle analysis to online algorithms. The idea is that rather than normalizing the performance of an online algorithm by an (optimal) offline algorithm, we explicitly express the behavior of the algorithm in terms of two more natural parameters: the size of the cache and Denning's working set measure. This technique creates a performance hierarchy of paging algorithms which better reflects their intuitive relative strengths. Also it reflects the intuition that a larger cache leads to a better performance. We obtain similar separation for list update algorithms. Lastly, we show that, surprisingly, certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results.</p
Exact and approximation algorithms for scheduling and placement problems
No full textDans cette thèse, nous nous intéressons à la résolution de quelques problèmes d'optimisation combinatoires que nous avons choisi de traiter en deux volets. Dans un premier temps, nous étudions des problèmes d'optimisation issus de l'ordonnancement d'un ensemble de tâches sur des machines de calcul et où on cherche à minimiser l'énergie totale consommée par ces machines tout en préservant une qualité de service acceptable. Dans un deuxième temps, nous traitons deux problèmes d'optimisation classiques à savoir un problème d'ordonnancement dans une architecture de machines parallèles avec des temps de communication, et un problème de placement de données dans des graphes modélisant des réseaux pair-à-pair et visant à minimiser le coût total d'accès aux données.In this thesis, we focus on solving some combinatorial optimization problems that we have chosen to study in two parts. Firstly, we study optimization problems issued from scheduling a set of tasks on computing machines where we seek to minimize the total energy consumed by these machines while maintaining acceptable quality of service. In a second step, we discuss two optimization problems, namely a classical scheduling problem in architecture of parallel machines with communication delays, and a problem of placing data in graphs that represent peer-to-peer networks and the goal is to minimize the total cost of data access
Online Dual Edge Coloring of Paths and Trees
No full textWe study a dual version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k , of available colors. All of our results are with regard to competitive analysis. For paths, we consider k=2 , and for trees, we consider any k≥2 . We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms on paths as well as trees. This is the first time that an optimal algorithm for online dual edge coloring has been identified for a class of graphs. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. Again, it is the first time that this has been done for a class of graphs. For trees, we also show that even randomized algorithms cannot be much better than First-Fit
Multi-Criteria TSP: Min and Max Combined
Get PDFWe present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized. For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3 − ε, 4 + ε) approximate Pareto curves. Here, the first parameter is the approximation ratio for the objectives that should be maximized, and the second parameter is the ratio for the objectives that should be minimized. For the asymmetric multi-criteria TSP (ATSP), we present an algorithm that computes (1/2 − ε, log2 n + ε) approximate Pareto curves. In order to obtain these results, we simplify the existing approximation algorithms for multi-criteria Max-STSP and Max-ATSP. Finally, we give algorithms with improved ratios for some special cases
Experimental algorithms: 14th international symposium, SEA 2015, Paris, France, June 29 - July 1, 2015, proceedings
No full textScheduling algorithms for energy and thermal management in computer systems
No full textLa gestion de la consommation d’énergie et de la température est devenue un enjeu crucial dans les systèmes informatiques. En effet, un grand centre de données consomme autant d’électricité qu’une ville et les processeurs modernes atteignent des températures importantes dégradant ainsi leurs performances et leur fiabilité. Dans cette thèse, nous étudions différents problèmes d’ordonnancement prenant en compte la consommation d’énergie et la température des processeurs en se focalisant sur leur complexité et leur approximabilité. Pour cela, nous utilisons le modèle de Yao et al. (1995) (modèle de variation de vitesse) pour la gestion d’énergie et le modèle de Chrobak et al. (2008) pour la gestion de la température.Nowadays, the enegy consumption and the heat dissipation of computing environments have emerged as crucial issues. Indeed, large data centers consume as muse electricity as a city while modern processors attain high temperatures degrading their performance and decreasing their reliability.. In this thesis, we study various energy and temperature aware scheduling problems and we focus on their complexity and approximability. A dominant technique for saving energy is by prosper scheduling of the jobs through the operating system combined with appropriate scaling of the processor's speed. This technique is referred to as speed scaling in the literature and its theoretical study was initiated by Yao, Demers and Shenker (FOCS'1995). In order to manage the thermal behavior of a computing device, we adaopt the approach of Chrobak, Dürr, Hurand and Robert (AAIM'2008). The main assumption is that some jobs are more CPU intensive than others and more heat is generated during their execution. Moreover, the cooling of a computing device occurs by introducing appropriate idle periods
On the generation of cutting planes which maximize the bound improvement
No full textWe propose a new cutting plane algorithm for Integer Linear Programming, which we refer to as the bound-optimal cutting plane method. The algorithm amounts to simultaneously generating k cuts which, when added to the linear programming relaxation, yield the (provably) largest bound improvement. We show that, in the general case, the corresponding cut generating problem can be cast as a Quadratically Constrained Quadratic Program. We also show that, for a large family of cuts, the latter can be reformulated as a Mixed-Integer Linear Program. We present computational experiments on the generation of bound-optimal stable set and cover inequalities for the max clique and knapsack problems. They show that, with respect to standard algorithms, the bound-optimal cutting plane method allows for a substantial reduction in the number of cuts and iterations needed to achieve either a given bound or an optimal solution
Algorithmes en ligne et d'approximation : au-delà des paradigmes pire cas
No full textCette thèse explore le paysage évolutif de l'analyse des algorithmes, des mesures traditionnelles du pire cas au cadre innovant des algorithmes learning augmented. Alors que l'analyse traditionnelle du pire cas a été au cœur des avancées de l'informatique théorique au cours des 50 dernières années, il existe de nombreux problèmes et algorithmes du monde réel pour lesquels l'analyse du pire cas ne fournit pas d'explication convaincante. Un exemple bien connu est le problème de la pagination en ligne, ou de la mise en cache. Dans la mise en cache, l'analyse du pire cas ne peut pas faire la distinction entre les méthodes FIFO et LRU, même si la méthode LRU est clairement supérieure en pratique. Cela sert de motivation pour explorer des approches qui vont au-delà de l'analyse du pire cas avec un accent particulier sur le domaine émergent des algorithmes avec prédictions (algorithmes learning augmented), qui a été inspiré par les progrès récents de la communauté de l'apprentissage automatique. Les algorithmes d'apprentissage automatique ont la capacité d'apprendre à partir de données passées et d'exploiter les modèles sous-jacents dans le domaine d'application, conduisant à des solutions étonnamment efficaces. Dans le cadre learning augmented, on conçoit des algorithmes qui fonctionnent en conjonction avec un modèle d'apprentissage automatique en boîte noire, qui leur fournit des informations prédictives sur les données. Étant donné que ces prédictions peuvent être sujettes à des erreurs, l'algorithme doit les gérer avec soin, une tâche qui introduit divers défis. Le cœur de notre travail réside dans les algorithmes en ligne, qui doivent prendre des décisions sans connaissance complète de la séquence d'entrée. Nous commençons par un problème purement en ligne qui illustre la nécessité d'une analyse au-delà du pire des cas. Le chapitre suivant explore une nouvelle variante d'un problème en ligne classique qui donne plus de puissance à l'algorithme en ligne en fournissant des informations supplémentaires sur l'entrée. Dans les deux chapitres suivants, nous étudions deux problèmes en ligne différents à travers le prisme des algorithmes learning augmented. Nous concevons des algorithmes utilisant des prédictions qui surmontent les barrières computationnelles connues lorsque les prédictions sont suffisamment précises. Même lorsque les prédictions sont mauvaises, nos algorithmes maintiennent toujours des garanties du pire des cas qui sont proches des meilleures garanties réalisables sans prédictions. Enfin, nous introduisons des schémas d'approximation learning augmented pour les problèmes d'optimisation NP-difficiles. Nous montrons que même un petit nombre de prédictions suffit à améliorer le temps d'exécution d'algorithmes d'approximation bien connus, dépassant les limites de calcul connues de l'analyse du pire cas.This thesis explores the evolving landscape of algorithm analysis, from the traditional worst-case metrics to the innovative framework of learning-augmented algorithms. While traditional worst-case analysis has been the core of advancements in theoretical computer science over the past 50 years, there are many real-world problems and algorithms for which worst-case analysis does not provide a convincing explanation. A well-known example is the online paging problem, or caching. In caching, worst-case analysis cannot distinguish between the FIFO and LRU methods, even though the LRU method is clearly superior in practice. This serves as a motivation to explore approaches that go beyond worst-case analysis with a particular focus on the emerging field of algorithms with predictions (learning-augmented algorithms), which has been inspired by the recent progress in the machine learning community. Machine learning algorithms have the ability to learn from past data and exploit underlying patterns in the application domain, leading to surprisingly effective solutions. In the learning-augmented framework, one designs algorithms that work in conjunction with a black-box machine learning model, which provides them with predictive information about the data. Since these predictions can be error-prone, the algorithm must handle them with care, a task that introduces various challenges. The core of our work lies in online algorithms, which must make decisions without complete knowledge of the input sequence. We begin with a purely online problem that illustrates the necessity for beyond worst-case analysis. The subsequent chapter explores a new variant of a classical online problem that gives more power to the online algorithm by providing additional information about the input. In the next two chapters, we study two different online problems through the lens of learning-augmented algorithms. We design algorithms using predictions that overcome known computational barriers when the predictions are accurate enough. Even when the predictions are bad, our algorithms still maintain worst-case guarantees that are close to the best achievable guarantees without predictions. Finally, we introduce learning-augmented approximation schemes for NP-hard optimization problems. We show that even a small number of predictions suffices to improve the running time of well-known approximation algorithms, surpassing known computational limits of worst-case analysis
- …
