Minimizing the weighted completion times (P ‖ Σ w_j C_j) and weighted number of tardy jobs (P ‖ Σ w_j U_j) on multiple identical machines are two classical NP-hard scheduling problems. As shown by Lenté et al. (2014), both problems can be solved in time ????^⋆(3ⁿ). In this paper, we improve these bounds to ????(2.755ⁿ) and ????^⋆(2ⁿ), respectively. Our algorithm for P ‖ Σ w_j C_j exploits the meet-in-the-middle paradigm and an efficient data structure answering linear programming queries. Additionally, when the number of machines is at most 6, we show that the running time for P ‖ Σ w_j C_j can further be improved. Both scheduling problems are generalizations of the classical Bin Packing problem, which can be solved in ????^⋆(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 ????((2-ε)ⁿ) for some ε > 0. Our algorithm makes use of two main ingredients: the recent ????((2-ε)ⁿ)-time algorithm of Nederlof et al. [SICOMP'23] for Bin Packing when the number of bins is a fixed constant, and the ????((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-08-25
2026-08-29