Arman Rouhani

In this thesis, we consider several scheduling problems inspired by practical applications. A scheduling problem concerns assigning tasks to a limited number of machines in order to optimize a given objective. The specific objective depends on the application. We use mathematical techniques to formulate these problems, analyze their structure, and identify the main challenges they present. We then design efficient algorithms that find optimal solutions whenever possible. However, many realistic variants are computationally hard, making optimal solutions difficult to obtain within a reasonable amount of time. This motivates the study of approximation algorithms. These algorithms trade optimality for efficiency, i.e., they do not guarantee an optimal solution but aim to efficiently produce solutions that are “good” enough with a provable guarantee on how far their value can be from the optimum. In this thesis, our focus is on theoretical approximation algorithms for scheduling problems. Chapter 2 presents an improved upper bound on the price of anarchy for scheduling games on related machines. The machines have different speeds and use the shortest processing time (SPT) rule for scheduling the jobs. Each job is controlled by a selfish player who aims to minimize its own completion time, while the social objective is to minimize the sum of completion times of all jobs. Our main result gives an upper bound of 2 − 1/(4m − 2) on the price of anarchy for the general case with m machines. We improve this bound to 3/2 for the case of two machines and to 2 − 1/(2m) for the general case with m machines when the machines have divisible speeds, i.e., when the speed of every machine is divisible by the speed of every slower machine. Chapter 3 studies a scheduling problem in a machine environment in which each machine must respect a predetermined order for processing the jobs. Given n jobs, each with a processing time and a deadline, we aim to minimize the number of machines used while respecting the deadlines and preserving the order on each machine. We show that the first-fit algorithm solves the problem optimally in the case of identical processing times and that it is a 2-approximation in the following cases: (1) the order is consistent with non-increasing slacks, (2) the order is consistent with non-decreasing slacks, (3) the order is consistent with non-increasing deadlines, and (4) the optimal solution uses at most three machines. Finally, we provide an algorithm with an O(log n) approximation factor for the general case. In Chapter 4, we present a dependent randomized rounding method that rounds fractional solutions to integral solutions that satisfy certain hard constraints on the output while preserving Chernoff-like concentration properties. In contrast to previous dependent rounding schemes, our algorithm guarantees that the cost of the rounded integral solution is not higher than that of the fractional solution. Our algorithm works for a class of assignment problems with restrictions similar to those of prior works. In a non-trivial combination of our general result with a classical approach of Shmoys and Tardos [101] and more recent linear programming techniques developed for the restricted assignment variant by Bansal and Sviridenko [11] and by Davies, Rothvoss, and Zhang [42], we derive an algorithm with an O(log n) approximation factor for the Budgeted Santa Claus Problem. In this new variant, the objective is to assign resources with different values to players, maximize the minimum value received by a player, and satisfy a budget constraint on the assignment costs between players and resources.