Online Algorithms for the Santa Claus Problem
Authors: Max Springer, MohammadTaghi Hajiaghayi, Debmalya Panigrahi, Mohammad Khani
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | 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 hajiagha@umd.edu Mohammad Reza Khani Microsoft Bing Ads Microsoft Corporation Redmond, WA khani87@gmail.com Debmalya Panigrahi Department of Computer Science Duke University Durham, NC debmalya@cs.duke.edu Max Springer Department of Mathematics University of Maryland College Park, MD mss423@umd.edu |
| 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 Define "(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. |