Submodular Order Functions and Assortment Optimization
Authors: Rajan Udwani
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We define a new class of set functions that in addition to being monotone and subadditive, also admit a very limited form of submodularity defined over a permutation of the ground set. We refer to this permutation as a submodular order. We give fast algorithms with strong approximation guarantees for maximizing submodular order functions under a variety of constraints. We also show an intriguing connection to the maximization of monotone submodular functions in the streaming model, where we recover best known approximation guarantees as a corollary of our results. |
| Researcher Affiliation | Academia | 1Department of IEOR, University of California, Berkeley, USA. Correspondence to: Rajan Udwani <rudwani@berkeley.edu>. |
| Pseudocode | Yes | ALGORITHM 1: 1/2 for Cardinality; ALGORITHM 2: Threshold Add(k, τ); ALGORITHM 3: 1/4 for Matroid Constraint; ALGORITHM 4: 1/3 for Budget; ALGORITHM 5: B-Threshold Add(B, τ); ALGORITHM 6: 0.5 for Budget Constraint; ALGORITHM 7: Final Add; ALGORITHM 8: Constrained Assortment Optimization for Compatible Choice Models |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | No | This paper is theoretical in nature, presenting algorithms and proofs without empirical evaluation on datasets, thus no training data information is provided. |
| Dataset Splits | No | This paper is theoretical in nature and does not involve empirical evaluation on datasets, therefore no validation split information is provided. |
| Hardware Specification | No | The paper is theoretical and focuses on algorithm design and approximation guarantees, thus it does not describe any specific hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not specify any software dependencies with version numbers, as it does not report on empirical experiments. |
| Experiment Setup | No | The paper is theoretical and does not include details such as hyperparameters or system-level training settings as part of an experimental setup. |