Algorithms with predictions
M Mitzenmacher, S Vassilvitskii - Communications of the ACM, 2022 - dl.acm.org
Algorithms with predictions Page 1 JULY 2022 | VOL. 65 | NO. 7 | COMMUNICATIONS OF
THE ACM 33 viewpoints IMA GE B Y ANDRIJ BOR YS A SSOCIA TE S, USING SHUTTERS T …
THE ACM 33 viewpoints IMA GE B Y ANDRIJ BOR YS A SSOCIA TE S, USING SHUTTERS T …
Learning predictions for algorithms with predictions
A burgeoning paradigm in algorithm design is the field of algorithms with predictions, in
which algorithms can take advantage of a possibly-imperfect prediction of some aspect of …
which algorithms can take advantage of a possibly-imperfect prediction of some aspect of …
Permutation predictions for non-clairvoyant scheduling
A Lindermayr, N Megow - Proceedings of the 34th ACM Symposium on …, 2022 - dl.acm.org
In non-clairvoyant scheduling, the task is to find an online strategy for scheduling jobs with a
priori unknown processing requirements with the objective to minimize the total (weighted) …
priori unknown processing requirements with the objective to minimize the total (weighted) …
Balanced allocations with the choice of noise
D Los, T Sauerwald - Journal of the ACM, 2023 - dl.acm.org
We consider the allocation of m balls (jobs) into n bins (servers). In the standard Two-Choice
process, at each step t= 1, 2,..., m we first sample two randomly chosen bins, compare their …
process, at each step t= 1, 2,..., m we first sample two randomly chosen bins, compare their …
A universal error measure for input predictions applied to online graph problems
G Bernardini, A Lindermayr… - Advances in …, 2022 - proceedings.neurips.cc
We introduce a novel measure for quantifying the error in input predictions. The error is
based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a …
based on a minimum-cost hyperedge cover in a suitably defined hypergraph and provides a …
A new toolbox for scheduling theory
Z Scully - ACM SIGMETRICS Performance Evaluation Review, 2023 - dl.acm.org
Queueing delays are ubiquitous in many domains, including computer systems, service
systems, communication networks, supply chains, and transportation. Queueing and …
systems, communication networks, supply chains, and transportation. Queueing and …
Performance of the Gittins policy in the G/G/1 and G/G/k, with and without setup times
We consider the classic problem of preemptively scheduling jobs of unknown size (aka
service time) in a queue to minimize mean number-in-system, or equivalently mean …
service time) in a queue to minimize mean number-in-system, or equivalently mean …
When Does the Gittins Policy Have Asymptotically Optimal Response Time Tail in the M/G/1?
Z Scully, L van Kreveld - Operations Research, 2024 - pubsonline.informs.org
We consider scheduling in the M/G/1 queue with unknown job sizes. It is known that the
Gittins policy minimizes mean response time in this setting. However, the behavior of the tail …
Gittins policy minimizes mean response time in this setting. However, the behavior of the tail …
Learning-augmented private algorithms for multiple quantile release
When applying differential privacy to sensitive data, we can often improve performance
using external information such as other sensitive data, public data, or human priors. We …
using external information such as other sensitive data, public data, or human priors. We …
Optimal Scheduling in Multiserver Queues
I Grosof - ACM SIGMETRICS Performance Evaluation Review, 2024 - dl.acm.org
Scheduling theory is a key tool for reducing latency (ie response time) in queueing systems.
Scheduling, ie choosing the order in which to serve jobs, can reduce response time by an …
Scheduling, ie choosing the order in which to serve jobs, can reduce response time by an …