We consider an assortment optimization problem where a customer chooses a
single item from a sequence of sets shown to her, while limited inventories
constrain the items offered to customers over time. In the special case where
all of the assortments have size one, our problem captures the online
stochastic matching with timeouts problem. For this problem, we derive a
polynomial-time approximation algorithm which earns at least 1-ln(2-1/e), or
0.51, of the optimum. This improves upon the previous-best approximation ratio
of 0.46, and furthermore, we show that it is tight. For the general assortment
problem, we establish the first constant-factor approximation ratio of 0.09 for
the case that different types of customers value items differently, and an
approximation ratio of 0.15 for the case that different customers value each
item the same. Our algorithms are based on rounding an LP relaxation for
multi-stage assortment optimization, and improve upon previous randomized
rounding schemes to derive the tight ratio of 1-ln(2-1/e).

我们考虑了一种混合物优化问题，针对在线随机匹配的情况，我们提出了一种多项式时间近似算法，其近似比为至少 1-ln (2-1 /e) 或 0.51，并基于线性规划松弛进一步改进了以前的随机舍入方案。在一般的混合物问题中，我们建立了第一个常数因子近似比为 0.09 的情况，这种情况下不同类型的客户赋予不同价值，并建立了近似比为 0.15 的情况，即不同客户赋予每个项目相同的价值。