Scheduling under Uncertainty: A Query-based Approach
Authors: Luciana Arantes, Evripidis Bampis, Alexander Kononov, Manthos Letsios, Giorgio Lucarelli, Pierre Sens
IJCAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We first give an optimal polynomial-time algorithm for the off-line error-query scheduling problem. For the on-line version of the problem, we prove that the competitive ratio of any on-line algorithm is Ω(k) even if the instance is laminar and agreeable and even if we search for only one free slot. Then, we propose a O(k)-competitive algorithm for laminar instances. Finally, in Section 4, we deal with the lexicographic error-query scheduling problem by matching lower and upper bounds of the competitive ratio for the on-line version. Table 1 summarizes our results. |
| Researcher Affiliation | Academia | 1 Sorbonne Universit e, CNRS, Laboratoire d Informatique de Paris 6, LIP6, F-75005 Paris, France 2 Sobolev Institute of Mathematics, Novosibirsk, Russia 3 Novosibirsk State University, Department of Mechanics and Mathematics, Russia 4 Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France |
| Pseudocode | Yes | Algorithm 1; Algorithm 2 |
| Open Source Code | No | The paper does not provide any concrete access to source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve training on a dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include an experimental setup with hyperparameters or system-level training settings. |