We study the problem of efficiently scheduling a computational DAG on multiple processors. The majority of previous works have developed and compared algorithms for this problem in relatively simple models; in contrast to this, we analyze this problem in a more realistic model that captures many real-world aspects, such as communication costs, synchronization costs, and the hierarchical structure of modern processing architectures. For this we extend the well-established BSP model of parallel computing with non-uniform memory access (NUMA) effects. We then develop a range of new scheduling algorithms to minimize the scheduling cost in this more complex setting: several initialization heuristics, a hill-climbing local search method, and several approaches that formulate (and solve) the scheduling problem as an Integer Linear Program (ILP). We combine these algorithms into a single framework, and conduct experiments on a diverse set of real-world computational DAGs to show that the resulting scheduler significantly outperforms both academic and practical baselines. In particular, even without NUMA effects, our scheduler finds solutions of 24%-44% smaller cost on average than the baselines, and in case of NUMA effects, it achieves up to a factor 2.5× improvement compared to the baselines. Finally, we also develop a multilevel scheduling algorithm, which provides up to almost a factor 5× improvement in the special case when the problem is dominated by very high communication costs.

We study the balanced k-way hypergraph partitioning problem, with a special focus on its practical applications to manycore scheduling. Given a hypergraph on n nodes, our goal is to partition the node set into k parts of size at most (1 + ∈)· n over k each, while minimizing the cost of the partitioning, defined as the number of cut hyperedges, possibly also weighted by the number of partitions they intersect. We show that this problem cannot be approximated to within a n1 / poly log log n factor of the optimal solution in polynomial time if the Exponential Time Hypothesis holds, even for hypergraphs of maximal degree 2. We also study the hardness of the partitioning problem from a parameterized complexity perspective, and in the more general case when we have multiple balance constraints.

Fair clustering enjoyed a surge of interest recently. One appealing way of integrating fairness aspects into classical clustering problems is by introducing multiple covering constraints. This is a natural generalization of the robust (or outlier) setting, which has been studied extensively and is amenable to a variety of classic algorithmic techniques. In contrast, for the case of multiple covering constraints (the so-called colorful setting), specialized techniques have only been developed recently for $k$-Center clustering variants, which is also the focus of this paper. While prior techniques assume covering constraints on the clients, they do not address additional constraints on the facilities, which has been extensively studied in non-colorful settings. In this paper, we present a quite versatile framework to deal with various constraints on the facilities in the colorful setting, by combining ideas from the iterative greedy procedure for Colorful $k$-Center by Inamdar and Varadarajan with new ingredients. To exemplify our framework, we show how it leads, for a constant number $γ$ of colors, to the first constant-factor approximations for both Colorful Matroid Supplier with respect to a linear matroid and Colorful Knapsack Supplier. In both cases, we readily get an $O(2^γ)$-approximation. Moreover, for Colorful Knapsack Supplier, we show that it is possible to obtain constant approximation guarantees that are independent of the number of colors $γ$, as long as $γ=O(1)$, which is needed to obtain a polynomial running time. More precisely, we obtain a $7$-approximation by extending a technique recently introduced by Jia, Sheth, and Svensson for Colorful $k$-Center.