A Parametrized Complexity View on Robust Scheduling with Budgeted Uncertainty

Noam Goldberg, Dvir Shabtay · 2026

Read A Parametrized Complexity View on Robust Scheduling with Budgeted Uncertainty by Noam Goldberg, Dvir Shabtay (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-02748.txt.

Description

Noam Goldberg and 1 co-author map exactly when robust scheduling under budgeted uncertainty is tractable, in a 2026 paper. One machine must sequence jobs whose processing times vary within a budget of total deviations. A job counts as tardy if any allowed scenario finishes it late, and the goal is minimizing tardy jobs. The problem is NP-hard in general.

Parameterized complexity gives the map. Against the robustness budget itself, the problem is W-one-hard yet solvable in XP time. Against the number of distinct due dates, it stays NP-hard even with only two due dates, but becomes pseudo-polynomial when that number is bounded. One common due date reduces the problem to a robust knapsack variant the authors solve in polynomial time. Against the number of jobs with nonzero deviations, the problem is fixed-parameter tractable. Each natural parameter draws its own border between feasible and hopeless.

Catalog record

CREATORNoam Goldberg, Dvir Shabtay
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE62 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-02748

Browse the full library · About the Tower of Babel