Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Online Algorithms for the Santa Claus Problem
Authors: Max Springer, MohammadTaghi Hajiaghayi, Debmalya Panigrahi, Mohammad Khani
NeurIPS 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment rule exists in the worst case. However, we show that, if the arrival order is random, then for n agents and any " > 0, we can obtain a competitive ratio of 1 " when the optimal assignment gives value at least (log n/"2) to every agent (assuming each item has at most unit value). We also show that this result is almost tight |
| Researcher Affiliation | Collaboration | Mohammad Taghi Hajiaghayi Department of Computer Science University of Maryland College Park, MD EMAIL Mohammad Reza Khani Microsoft Bing Ads Microsoft Corporation Redmond, WA EMAIL Debmalya Panigrahi Department of Computer Science Duke University Durham, NC EMAIL Max Springer Department of Mathematics University of Maryland College Park, MD EMAIL |
| Pseudocode | Yes | The pseudocode of this procedure is presented in Algorithm 1. ALGORITHM 1: SMOOTH GREEDY WITH RESTART Input: 0 < " < 1, input stream M of m items Deο¬ne "(u) = 1/" log(Pi=1 e"ui); for t = 1 to m/2 do Select xt n to maximize "(P m/2 i=1 xi + xt) end for t = m/2 + 1 to m do Select xt n to maximize "(P m i=m/2+1 xi + xt) end for |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. There are no repository links or explicit code release statements. |
| Open Datasets | No | The paper is theoretical and does not use or reference any datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not discuss dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not specify any hardware details used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific details like hyperparameter values or training configurations. |