The cost of being restricted by time, knowledge or fairness in scheduling and allocation problems

Abstract

In dieser Dissertation untersuchen wir Probleme, deren Lösungen unter gewissen Einschränkungen gefunden werden müssen. Die Qualität unserer Algorithmen messen wir durch den Vergleich mit der optimalen Lösung. Online-Algorithmen sind mit einem Optimierungsproblem konfrontiert und müssen Entscheidungen treffen, ohne vollständige Kenntnis der Eingabe zu haben. Die Informationen werden dem Algorithmus erst nach und nach übermittelt. Wir messen die Qualität eines Online-Algorithmus mithilfe des Kompetitivitätsverhältnisses. Dies ist das Maximum (oder Supremum) des Verhältnisses zwischen dem Wert des Algorithmus und dem optimalen Wert über allen Eingaben. Offline-Approximations-Algorithmen müssen eine Lösung in polynomieller Zeit finden und werden ebenfalls mit einem optimalen Algorithmus verglichen. Dieser Vergleich wird Approximationsverhältnis genannt und ist analog zum Kompetitivitätsverhältnis definiert. Wenn wir Güter oder Aufgaben verteilen, dann definieren wir den Preis der Fairness. Dieser vergleicht das von einer fairen Verteilung erzielte Allgemeinwohl mit dem von einer optimalen Verteilung erreichten. Im Buffer-Minimierungsproblem mit Konflikten ist ein Graph gegeben, in dem die Knoten Prozessoren und die Kanten Konflikte darstellen. Jederzeit kann Last auf den Knoten ankommen, die verarbeitet werden muss. Die Prozessoren speichern diese Last in einem Buffer. Ziel ist es, die Last zu verarbeiten und dabei die maximal notwendige Buffergröße klein zu halten. Wir führen hier ein neues Modell, Flow Model genannt, ein und bestimmen das Kompetitivitätsverhältnis auf einem Pfad mit bis zu 5 Maschinen. Zusätzlich betrachten wir Algorithmen mit Ressourcenaugmentation auf allgemeinen Graphen. Im diskreten bamboo garden trimming problem wachsen n Bambusse mit Geschwindigkeit v_1, . . . , v_n pro Tag. Jeden Tag wird ein Bambus auf Höhe null geschnitten. Ziel ist es, die Höhe des größten Bambus gering zu halten. Wir verbessern das Approximationsverhältnis auf den Wert 7/5, indem wir das Problem auf das pinwheel-scheduling problem zurückführen. Darüber hinaus betrachten wir die kontinuierliche Version, in der sich der Gärtner zwischen den Pflanzen bewegt, und finden konstante Approximationsalgorithmen für den Fall, dass die Pflanzen auf einem Sterngraph angeordnet sind. In bisherigen Arbeiten wurde die faire Verteilung von teilbaren und unteilbaren Gütern sowie von teilbaren Aufgaben behandelt. Wir widmen uns der Verteilung von unteilbaren Aufgaben und zeigen, wann bestimmte faire Verteilungen existieren und bestimmen die Preise der Fairness für dieses Problem.

In this thesis, we consider a variety of problems where solutions must be found while adhering to some kind of restriction. We measure the performance of our algorithms by comparing them to optimal solutions. Online algorithms face an optimization problem and must find a solution with incomplete knowledge of the input. Their performance is measured using the competitive ratio. For a minimization problem this is the maximum (or supremum) of the value achieved by the algorithm divided by the optimal value over all instances. Offline approximation algorithms must find a solution in polynomial time and are compared to an optimal algorithm using the approximation ratio that is defined analogously to the competitive ratio. Finally, when allocating goods or chores we can define the price of fairness which compares the welfare of an allocation that adheres to some notion of fairness to the welfare of an optimal allocation. In the buffer minimization problem with conflicts we are given a graph where the nodes represent processors and the edges represent conflicts. At any time tasks may arrive on a processor adding to this processor’s workload. Each processor stores its workload in a separate input buffer. The goal is to find a scheduling strategy that minimizes the maximum used buffer size of all processors. We introduce a new model called the flow model, where load may not arrive in blocks but instead arrives at a fixed rate. We discuss a variety of results, including tight or almost tight competitive ratios for both the original and the flow model on the path with up to five machines. We also slightly improve the lower bound on the path with m machines and discuss algorithms with resource augmentation that achieve good results on general graphs. In the discrete bamboo garden trimming problem, we are given a set of n bamboo that grow at rates v1, . . . , vn per day. Initially, the height of all plants is zero. Each day a robotic gardener cuts down one bamboo to height zero. The goal is to design a trimming schedule such that the height of the tallest bamboo that is ever achieved is minimized. For this problem we improve the approximation ratio to 7/5 using a reduction to the pinwheel-scheduling problem. We also consider the continuous version of the problem, where the gardener travels between plants in a metric space, and find algorithms with constant approximation ratios for the case where this metric is a star graph. Previous work has discussed the fair allocation of indivisible and divisible goods as well as divisible chores and we fill a gap in the literature by considering the problem of allocating contiguous blocks of indivisible chores fairly. We show the existence of certain types of fair allocations and find the prices of fairness for the commonly used notions of fairness.