abstract: Graph coloring is about allocating resources that can be shared except where there are certain pairwise conflicts between recipients. The simplest coloring algorithm that attempts to conserve resources is called first fit. Interval graphs are used in models for scheduling (in computer science and operations research) and in biochemistry for one-dimensional molecules such as genetic material. It is not known precisely how much waste in the worst case is due to the first-fit algorithm for coloring interval graphs. However, after decades of research the range is narrow. Kierstead proved that the performance ratio R is at most 40. Pemmaraju, Raman, and Varadarajan proved that R is at most 10. This can be improved to 8. Witsenhausen, and independently Chrobak and Slusarek, proved that R is at least 4. Slusarek improved this to 4.45. Kierstead and Trotter extended the method of Chrobak and Slusarek to one good for a lower bound of 4.99999 or so. The method relies on number sequences with a certain property of order. It is shown here that each sequence considered in the construction satisfies a linear recurrence; that R is at least 5; that the Fibonacci sequence is in some sense minimally useless for the construction; and that the Fibonacci sequence is a point of accumulation in some space for the useful sequences of the construction. Limitations of all earlier constructions are revealed. / Dissertation/Thesis / Ph.D. Mathematics 2010

abstract: A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs. / Dissertation/Thesis / Ph.D. Mathematics 2012

At Halmstad University a project was developed to provide recommendations forupgrading and downgrading the cloud resource app service plan based on the customersusage over the last 30 days. In today’s day and age, cloud resources and services are oftenquite expensive and offers a variety of different plans which can make it overwhelmingfor the customer to easily choose which tier they need for their plan. The result of thisscript indicate that the cloud users should consider changing subscription tier based onhow the historical data of their usage of the plan has looked like during the last 30 days.The proposed algorithm suggests an upgrade of a tier if the plan is overutilized andsuggest a downgrade of a tier if the plan is underutilized. The developed PowerShell codeuses the First-Fit and the Rule-based algorithmic approach from the related workresearched in the paper. The result found was that the code was able to give suitablerecommendations to scale up and down tiers for plans which were under and overutilizedbased on the percentual utilization rules set up and Legacy/DEV SKU mapping. Theresults obtained showed that the suggested plan can reduce costs by up to 30% and giveroughly 438.2% more performance per $USD spent. / Vid Högskolan i Halmstad utvecklades ett projekt för att ge förslag på uppgraderingaroch nedgraderingar av molnresursern app service plan baserat på användarens senaste 30dagars användning. Då dagens molnresurser och tjänster ofta är dyra och erbjuder ettöverflöd av planer, kan det vara förvirrande för användare att välja rätt nivå för sinabehov. Projektet föreslår att användarna ska överväga att byta plan beroende på hur denhistoriska datan har sett ut för planens användning, där en uppgradering rekommenderasom tjänsten är överanvänd och en nedgradering om planen är underanvänd. Denutvecklade PowerShell koden använder sig av First-fit och det regelbaserade algoritmtypen som utvecklades med inspiration från litteraturstudien. Resultatet av projektetindikerar att koden kunde ge optimala upp och ned skalnings rekommendationer beroendepå de olika procentuella trösklarna satta samt mappningen av Legacy och utvecklingstiers. Analyseringen av resultatet pekar på att det går att spara runt 30% på app serviceplan kostnaderna samt att app service planerna får 438,2% mer prestanda per spenderad$USD i jämförelse med nuvarande planen.

No description available.

La planification et la gestion optimale des ressources humaines jouent un rôle important dans la productivité et la compétitivité des entreprises. Dans cette thèse nous nous intéressons à la modélisation et à la résolution de différents problèmes d'optimisation soulevés par la construction de plannings pour les agents qui travaillent dans un contexte aéronautique : la création de vacations, la création de rotation, l'affectation de vacations et de rotations. Pour le problème de construction de vacations, nous proposons une approche de modélisation basée sur le concept de plage horaire et ensuite une méthode heuristique de résolution basée sur l'algorithme FFD (First Fit Decreasing) et sur la génération de colonnes. Le problème de création de rotations est résolu par une méthode de programmation linéaire en variables mixtes. Les problèmes d'affectation de vacations et de rotations sont modélisés comme des problèmes de multi-affectation généralisé. Nous proposons une décomposition temporelle et par qualification et ensuite une transformation du problème d'affectation généralisé en un problème d'affectation simple par relaxation Lagrangienne. Un algorithme ad-hoc est utilisé pour la résolution de chaque problème de base. La plupart des algorithmes élaborés ont été couplés à des bases de données réelles et commercialisés par la société IFR-France.

This thesis describes design and implementation of effective memory management for multi-threaded applications. At first, the virtual memory possibilities are described, which can be found in the latest operating systems, such as Microsoft Windows and Linux. Afterwards the most frequently used algorithms for memory management are explained. Consequently, their features are used properly for a new memory manager. Final design includes particular tools for application debugging and profiling. At the end of the thesis a series of tests and evaluation of achieved results were done.