Online Unrelated Machine Load Balancing with Predictions Revisited
Authors: Shi Li, Jiayi Xian
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | First, we design deterministic and randomized online rounding algorithms for the problem in the unrelated machine setting, with O log m log log m and O log log m log log log m -competitive ratios. They respectively improve upon the previous ratios of O(log m) and O(log3 log m), and match the lower bounds given by Lattanzi et al. Second, we extend their prediction scheme from the identical machine restricted assignment setting to the unrelated machine setting. With the knowledge of two vectors over machines, a dual vector and a weight vector, we can construct a good fractional assignment online, that can be passed to an online rounding algorithm. Finally, we consider the learning model introduced by Lavastida et al. (2020), and show that under the model, the two vectors can be learned efficiently with a few samples of instances. |
| Researcher Affiliation | Academia | 1Department of Computer Science and Engineering, University at Buffalo, Buffalo, NY, USA. Research is supported in part by NSF grant CCF-1844890. Correspondence to: Shi Li <shil@buffalo.edu>, Jiayi Xian <jxian@buffalo.edu>. |
| Pseudocode | Yes | Algorithm 1 Algorithm in Stage 2 Algorithm 2 construction of initial β |
| Open Source Code | No | The paper does not provide any concrete access information (specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described in this paper. |
| Open Datasets | No | The paper is theoretical and does not perform empirical experiments with datasets. Therefore, it does not provide concrete access information for a publicly available or open dataset. |
| Dataset Splits | No | The paper is theoretical and does not perform empirical experiments with datasets. Therefore, it does not provide specific dataset split information needed to reproduce the data partitioning. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any specific ancillary software details (e.g., library or solver names with version numbers) needed to replicate experiments. |
| Experiment Setup | No | The paper is theoretical and does not describe any specific experimental setup details (concrete hyperparameter values, training configurations, or system-level settings). |