Minimizing the weighted completion times (P || ΣwⱼCⱼ) and weighted number of tardy jobs (P || ΣwⱼCⱼ) on multiple identical machines are two classical NP-hard problems in the scheduling community. As shown by Lenté et al. (2014), both problems can be solved in time O*(3ⁿ). In this paper, we improve upon this bound to O(2.755ⁿ) and O(2.890ⁿ) respectively. Interestingly, the algorithm for P || ΣwⱼCⱼ exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, for a fixed number of machines at most 6, we show that the running time for P || ΣwⱼCⱼ can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in O*(2ⁿ) time. Improving this running time is an important open question. We show that, when assuming the Asymptotic Rank Conjecture (ARC), Bin Packing can be solved in time O((2-ε)ⁿ) for some ε > 0. Our algorithm makes use of two main ingredients: the recent O((2-ε)ⁿ)-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the O((2-ε)ⁿ)-time algorithm of Björklund et al. [SODA'25] for special instances of the 3-way Partitioning problem when assuming ARC.
European Symposium on Algorithms (ESA)
2026-06-26
2026-07-28