Algorithmic Advances in Allocation and Scheduling

We design new and improved approximation algorithms for classical problems in machine scheduling and resource allocation. In the machine scheduling problem we consider, we are given a set of jobs $J$ with processing times $p_j$ for each $j \in J$. Further, a job $j$ may be scheduled only on some subset of machines $S_j \subseteq M$. The goal is to find an assignment of jobs to machines to minimize the time by which all jobs can be processed. The input for the resource allocation problem we consider is identical after treating the jobs as resources and machines as players respectively. The goal, however, is different: we want to assign resources to the players while ensuring that every player receives resources totaling value at least $\tau$ for the largest possible $\tau$. This corresponds to maximizing a natural notion of fairness. Our techniques for improving the state of the art for both problems are versatile. We demonstrate their applicability in developing an efficient hypergraph generalization of the Hungarian algorithm for finding perfect matchings in bipartite graphs