Non-clairvoyant Scheduling with Partial Predictions

arXiv:2405.01013v1 Announce Type: new
Abstract: The non-clairvoyant scheduling problem has gained new interest within learning-augmented algorithms, where the decision-maker is equipped with predictions without any quality guarantees. In practical settings, access to predictions may be reduced to specific instances, due to cost or data limitations. Our investigation focuses on scenarios where predictions for only $B$ job sizes out of $n$ are available to the algorithm. We first establish near-optimal lower bounds and algorithms in the case of perfect predictions. Subsequently, …

abstract access algorithms arxiv cost cs.ai cs.ds cs.lg data decision instances investigation limitations maker practical predictions quality scheduling type