We study the restricted case of Scheduling on Unrelated Parallel Machines. In this problem, we are given a set of jobs $J$ with processing times $p_j$ and each job 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 within which all jobs can be processed. In a seminal paper, Lenstra, Shmoys, and Tardos [ Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] designed an elegant 2-approximation for the problem. The question of whether approximation algorithms with better guarantees exist for this classic scheduling problem has since remained a source of mystery. In recent years, with the improvement of our understanding of configuration linear programs, it now appears an attainable goal to design such an algorithm. Our main contribution in this paper is to make progress towards this goal. For the so-called $(1,\epsilon)$-case, when the processing times of jobs are either $1$ or $\epsilon \in (0,1)$, we design an approximation algorithm whose guarantee tends to $1 + \sqrt{3}/2 \approx 1.866025$ as $\epsilon$ tends to zero. This improves on the $2-\epsilon_0$ guarantee recently obtained by Chakrabarty, Khanna, and Li [ Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2015, pp. 1087--1101] for some constant $\epsilon_0 > 0$. Further, the ideas presented in this paper do not crucially depend on the fact that the instances contain exactly two different job sizes; i.e., they extend also to families of instances more general than the $(1,\epsilon)$-case. In a certain precise sense, we fall slightly short of improving on the 30-year-old classic algorithm of Lenstra, Shmoys, and Tardos [ Proceedings of the 28th Annual IEEE Conference on Foundations of Computer Science, 1987, pp. 217--224] for the restricted case.

We study the basic allocation problem of assigning resources to players to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain Configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4+ ε. In contrast, however, the best-known approximation algorithm for the problem has an unspecified large constant guarantee. In this article, we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [13] for hypergraph matchings and later used in this context by Asadpour, Feige, and Saberi [2]. For our local search procedure to terminate in polynomial time, we introduce several new ideas, such as lazy updates and greedy players . Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the Configuration-LP only in the analysis.

Haxell's condition [16] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perfect matching in the bipartite hypergraph. Unlike in graphs, however, there is no known polynomial time algorithm to find the hypergraph perfect matching that is guaranteed to exist when Haxell's condition is satisfied.

We study the basic allocation problem of assigning resources to players so as to maximize fairness. This is one of the few natural problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, a certain configuration-LP can be used to estimate the value of the optimal allocation to within a factor of 4 + ε. In contrast, however, the best known approximation algorithm for the problem has an unspecified large constant guarantee. In this paper we significantly narrow this gap by giving a 13-approximation algorithm for the problem. Our approach develops a local search technique introduced by Haxell [11] for hypergraph matchings, and later used in this context by Asadpour, Feige, and Saberi [1]. For our local search procedure to terminate in polynomial time, we introduce several new ideas such as lazy updates and greedy players. Besides the improved approximation guarantee, the highlight of our approach is that it is purely combinatorial and uses the configuration-LP only in the analysis.