2026-08-25T18:47:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27189 2026-08-25T13:18:17Z ddc:004 open_access

Faster Exponential Algorithms for Multi-Machine Scheduling Problems Dhar, Anubhav Dürr, Anita Ghazy, Ahmed Greilhuber, Jakob Węgrzycki, Karol Scheduling exact algorithms exponential-time algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anubhav Dhar and Anita Dürr and Ahmed Ghazy and Jakob Greilhuber and Karol Węgrzycki 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.53 urn:nbn:de:0030-drops-271894 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.53 eng https://creativecommons.org/licenses/by/4.0/legalcode