Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908852497154048 |
|---|---|
| author | Jeang, John Podolskii, Vladimir |
| author_facet | Jeang, John Podolskii, Vladimir |
| contents | In the One-Fast-Many-Slow decision problem, introduced by Sheffield and Westover (ITCS '25), a scheduler, with access to one fast machine and infinitely many slow machines, receives a series of tasks and must allocate the work among its machines. The goal is to minimize the overhead of an online algorithm over the optimal offline algorithm. Three versions of this setting were considered: Instantly-committing schedulers that must assign tasks to machines immediately and irrevocably, Eventually-committing schedulers whose assignments are irrevocable but can occur anytime after a task arrives, and Never-committing schedulers that can interrupt and restart a task on a different machine. In the Instantly-committing model, Sheffield and Westover showed that the optimal competitive ratio is equal to 2, while in the Eventually-committing model the competitive ratio lies in the interval [1.618, 1.678], and in the Never-committing model the competitive ratio lies in the interval [1.366, 1.5] (SPAA '24, ITCS '25). In the latter two models, the exact optimal competitive ratios were left as open problems, moreover Kuszmaul and Westover (SPAA '24) conjectured that the lower bound in the Eventually-committing model is tight.
In this paper we resolve this problem by providing tight bounds for the competitive ratios in the Eventually-committing and Never-committing models. For Eventually-committing, we prove Kuszmaul and Westover's conjecture by giving an algorithm achieving a competitive ratio equal to the lower bound of $\frac{1+\sqrt{5}}{2}\approx 1.618$. For Never-committing, we provide an explicit Task Arrival Process (TAP) lower bounding the competitive ratio to the previous upper bound of 1.5. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_22108 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting Jeang, John Podolskii, Vladimir Data Structures and Algorithms In the One-Fast-Many-Slow decision problem, introduced by Sheffield and Westover (ITCS '25), a scheduler, with access to one fast machine and infinitely many slow machines, receives a series of tasks and must allocate the work among its machines. The goal is to minimize the overhead of an online algorithm over the optimal offline algorithm. Three versions of this setting were considered: Instantly-committing schedulers that must assign tasks to machines immediately and irrevocably, Eventually-committing schedulers whose assignments are irrevocable but can occur anytime after a task arrives, and Never-committing schedulers that can interrupt and restart a task on a different machine. In the Instantly-committing model, Sheffield and Westover showed that the optimal competitive ratio is equal to 2, while in the Eventually-committing model the competitive ratio lies in the interval [1.618, 1.678], and in the Never-committing model the competitive ratio lies in the interval [1.366, 1.5] (SPAA '24, ITCS '25). In the latter two models, the exact optimal competitive ratios were left as open problems, moreover Kuszmaul and Westover (SPAA '24) conjectured that the lower bound in the Eventually-committing model is tight. In this paper we resolve this problem by providing tight bounds for the competitive ratios in the Eventually-committing and Never-committing models. For Eventually-committing, we prove Kuszmaul and Westover's conjecture by giving an algorithm achieving a competitive ratio equal to the lower bound of $\frac{1+\sqrt{5}}{2}\approx 1.618$. For Never-committing, we provide an explicit Task Arrival Process (TAP) lower bounding the competitive ratio to the previous upper bound of 1.5. |
| title | Tight Bounds for Online Scheduling in the One-Fast-Many-Slow Machines Setting |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.22108 |