Approximation Algorithms for Capacitated k-Median and Scheduling with Resource and Precedence Constraints

This thesis proposes approximation algorithms for two combinatorial optimization problems: 1) Capacitated k-Median, and 2) Scheduling with Resource and Precedence Constraints. In the first problem, we are given a set of clients and a set of facilities in a metric space such that a set of k facilities need to be opened and each client needs to be assigned to an open facility (clustered around) to minimize the sum of client-facility distances. In addition, we have capacity constraints associated with each facility in the input to indicate the maximum number of clients that can be assigned to that facility. We give a constant-factor approximation algorithm for this problem by rounding a linear programming relaxation. In line with the previous approximation algorithms for the same problem, this is a pseudo-approximation algorithm that violates the capacities by at most a factor of (1+ epsilon). In the second problem, we have a set of jobs to be scheduled on a set of machines to minimize either the makespan of the schedule or the more general total weighted completion time. Jobs have precedence constraints between them. Each job also have a resource requirement and the total resource use of jobs running concurrently at any point in a feasible schedule should not exceed the global resource cap given in the input. We initially use a divide-and-conquer approach to obtain a O(log n)-approximation for the minimum makespan objective on identical machines. Then, we generalize the result to weighted completion time objective and uniformly related machines by combining the initial divide-and-conquer method with linear programming relaxations for these variations. Furthermore, we adapt our algorithm as a solution to an emerging problem in High Performance Computing (HPC): scheduling precedence constrained jobs under a power cap. We implement our algorithm and compare it to state-of-the-art greedy methods in a simulation environment on a variety of precedence relationships and power/performance data collected from real HPC applications. We find that our divide-and-conquer method improves performance by up to 75% compared to greedy scheduling algorithms