Advice Querying under Budget Constraint for Online Algorithms
Authors: Ziyad Benomar, Vianney Perchet
NeurIPS 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Finally, we run simulations of our algorithms in Section 5. We show that the performance of the algorithm we introduced for the secretary problem matches our theoretical lower bound, and we compare it to another heuristic version that we did not study theoretically. Then, by exhaustively testing the algorithm we designed for the scheduling problem with access B job sizes on various benchmark instances, we observe that it has a better performance in practice than the theoretical upper bound 2 (B/N)2. |
| Researcher Affiliation | Collaboration | Ziyad Benomar CREST, ENSAE, Ecole polytechique ziyad.benomar@ensae.fr Vianney Perchet CREST, ENSAE and Criteo AI LAB vianney.perchet@normalesup.org |
| Pseudocode | Yes | Algorithm 1: Deterministic algorithm with input binary prediction [47]; Algorithm 2: Randomized algorithm with input binary prediction [47]; Algorithm 3: ADATHRESH Adaptive Threshold; Algorithm 4: PAR Parallel algorithm with Adaptive processing Rate; Algorithm 5: ADATHRESH with memory |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the described methodology, nor does it provide links to a code repository. |
| Open Datasets | No | The paper describes generating synthetic data for experiments (e.g., 'number of snow days is sampled randomly from a uniform distribution in [1, 4b]', 'jobs having (i) identical sizes, (ii) sizes sampled from the exponential distribution, (iii) uniform distribution, (iv) and Pareto distribution'), but it does not refer to or provide access information for any publicly available or open datasets. |
| Dataset Splits | No | The paper describes running simulations and experiments but does not provide specific details on dataset splitting (e.g., train/validation/test splits, percentages, or sample counts) for reproduction. |
| Hardware Specification | No | The paper does not provide any specific details regarding the hardware used to run the experiments, such as GPU/CPU models, memory, or specific computer specifications. |
| Software Dependencies | No | The paper describes the algorithms and their theoretical analysis and experimental results, but it does not list any specific software dependencies with version numbers (e.g., Python, PyTorch, specific solvers) that would be needed to reproduce the experiments. |
| Experiment Setup | Yes | For the ski-rental problem, we set a buying cost of b = 50 for Figure 5 and b = 100 for Figure 6, and the number of snow days is sampled randomly from a uniform distribution in [1, 4b]. Each point in both figures is computed over 10^5 simulations. The value of λ is chosen optimally with respect to p as indicated in Lemmas 2.2 and 2.3. ... In Figure 7, we test ADATHRESH with N = 1000... We test it with N = 50 and jobs having (i) identical sizes, (ii) sizes sampled from the exponential distribution, (iii) uniform distribution, (iv) and Pareto distribution. ... Each point in the figure was obtained by averaging over 10000 runs. |