Minimalistic Predictions for Online Class Constraint Scheduling
Authors: Dorian Guyot, Alexandra Lassota
ICLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present new algorithms with competitive ratios independent of m and tight lower bounds for several classical and problem-specific prediction models. We thereby give a structured overview of what additional information helps in the design of better scheduling algorithms. In this paper, we show the following algorithms, where ℓis the error of the respective prediction: For minimizing the makespan for online class constraint scheduling on m identical machines, there is an algorithm with predicted input with a competitive ratio at most (ℓ/OPT + α) where OPT is an offline optimal solution and α is the competitive ratio of an offline approximation algorithm (see Theorem 3). Finally, we prove all of our competitive algorithms to be (nearly) tight, i.e., no algorithm with access to the same predictions can yield a (significantly) better competitive ratio (see Theorems 4, 7, and 12). |
| Researcher Affiliation | Academia | Dorian Guyot University of Fribourg Fribourg, Switzerland EMAIL Alexandra Lassota Eindhoven University of Technology Eindhoven, The Netherlands EMAIL |
| Pseudocode | No | The paper describes algorithms (Full Input Prediction Algorithm, Action Prediction Algorithm, Class Size Predictions Algorithm) in structured steps using bullet points, but it does not use explicit "Pseudocode" or "Algorithm" labels with code-like formatting. For example, the "Class Size Predictions Algorithm" section describes three steps in text, but not in a pseudocode block. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code, providing links to code repositories, or mentioning code in supplementary materials. |
| Open Datasets | No | The paper defines abstract problem instances (e.g., 'given m machines and n jobs with job j having processing time pj and class cj') and focuses on theoretical algorithm design and analysis. It does not mention using or providing access to any specific datasets for empirical evaluation. |
| Dataset Splits | No | The paper does not use specific datasets for empirical evaluation, and therefore, no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical, focusing on algorithm design and proofs of competitive ratios. There is no mention of hardware used for experiments. |
| Software Dependencies | No | The paper discusses algorithms and their theoretical running times (e.g., 'O(nmk)'), but does not mention specific software packages or libraries with version numbers required for implementation. |
| Experiment Setup | No | The paper is theoretical and focuses on algorithm design and analysis, not empirical experiments. Therefore, no experimental setup details such as hyperparameters or training configurations are provided. |