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
| CREATOR | Noam Goldberg, Dvir Shabtay |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-02748