Online Weighted Paging with Unknown Weights
Authors: Orin Levy, Noam Touitou, Aviv Rosenberg
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present the first algorithm for online weighted paging that does not know page weights in advance, but rather learns from weight samples. In terms of techniques, this requires providing (integral) samples to a fractional solver, requiring a delicate interface between this solver and the randomized rounding scheme; we believe that our work can inspire online algorithms to other problems that involve cost sampling. (From the NeurIPS checklist: This is a theory paper that present an algorithm for the online weighted paging where the weight are unknown and prove the stated bounds.) |
| Researcher Affiliation | Collaboration | Orin Levy Tel-Aviv University orinlevy@mail.tau.ac.il Noam Touitou Amazon Science noamtwx@gmail.com Aviv Rosenberg Google Research avivros007@gmail.com |
| Pseudocode | Yes | Algorithm 1: Fractional Online Weighted Caching with Unknown Weights, Algorithm 2: Randomized rounding algorithm for OWP-UW, Algorithm 3: Rebalancing procedure for randomized algorithm, Algorithm 4: Optimistic-Pessimistic Weights Estimation Procedure |
| Open Source Code | No | The paper is theoretical and does not mention providing open-source code for its methodology. |
| Open Datasets | No | The paper is theoretical and does not involve the use of datasets for training or experimentation. |
| Dataset Splits | No | The paper is theoretical and does not describe any validation dataset splits as it does not conduct experiments. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware specifications for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not provide details on experimental setup or hyperparameters as it does not conduct experiments. |