Submodular Order Functions and Assortment Optimization
定义了一类新的集合函数（次模序函数），并给出在多种约束下最大化该函数的快速算法和近似保证，应用于品类优化问题，得到更快且近似比更强的算法。
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. This class of functions includes monotone submodular functions as a subfamily. We give fast algorithms with strong approximation guarantees for maximizing submodular order functions under a variety of constraints and show a nearly tight upper bound on the highest approximation guarantee achievable by algorithms with polynomial query complexity. Applying this new notion to the problem of constrained assortment optimization in fundamental choice models, we obtain new algorithms that are both faster and have stronger approximation guarantees (in some cases, first algorithm with constant factor guarantee). 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. This paper was accepted by Chung Piaw Teo, optimization. Funding: This work was supported by the NSF Division of Civil, Mechanical, and Manufacturing Innovation [Grant 2340306] and Google Research Scholar Program. Supplemental Material: The online appendices are available at https://doi.org/10.1287/mnsc.2021.04108 .