Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
复制标题
通过连续 LP 揭示广义秘书问题的最佳阈值：对在线 K 物品拍卖和随机到达顺序的双向 K 匹配的影响
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Jiang
中科院分区：
文献类型：
--
作者：
T;Fei Chen;S. Jiang
我们考虑一般的 (J, K) 秘书问题，其中 n 个完全有序的项目以随机顺序到达。算法观察到达项目的相对优点并允许做出 J 个选择。目标是最大化 K 个最佳项目中选择的项目的预期数量。
Buchbinder、Jain 和 Singh 提出了一种有限线性规划（LP），可以完整地表征该问题，但由于 n 趋于无穷大，因此很难分析其最优解的渐近行为。相反，我们证明了有限模型和无限模型之间的形式联系，其中存在可数无限数量的项目，每个项目的到达时间都是从 [0, 1] 独立且统一地得出的。
有限 LP 扩展到连续 LP，其互补松弛条件揭示了一种最优算法，其中涉及 JK 阈值，其作用与最优经典秘书算法中的 1/e 阈值类似。特别是，对于K=1的情况，J个最优阈值有很好的“理性描述”。我们持续的LP分析为问题提供了非常清晰的视角，新的见解激励我们解决两个相关的问题。
1. 我们解决了仅基于相对优点的算法是否可以实现拟阵秘书问题的最优比率的开放问题。我们表明，对于随机到达投标的在线 2 项拍卖（K = 2 的 K 均匀拟阵问题），仅基于相对优点做出决策的算法无法实现最佳比率。这与民间传说形成鲜明对比，即对于在线 1 件物品拍卖，任何算法的性能比都不能严格大于 1/e，而这可以通过仅考虑相对优点的算法来实现。
2. 我们给出了一种通用的变换技术，对于（K，K）秘书问题采用任何单调算法（例如阈值算法），并构造一种具有至少相同性能保证的具有随机到达顺序的在线二分K匹配算法。
We consider the general (J, K)-secretary problem, where n totally ordered items arrive in a random order. An algorithm observes the relative merits of arriving items and is allowed to make J selections. The objective is to maximize the expected number of items selected among the K best items.
Buchbinder, Jain and Singh proposed a finite linear program (LP) that completely characterizes the problem, but it is difficult to analyze the asymptotic behavior of its optimal solution as n tends to infinity. Instead, we prove a formal connection between the finite model and an infinite model, where there are a countably infinite number of items, each of which has arrival time drawn independently and uniformly from [0, 1].
The finite LP extends to a continuous LP, whose complementary slackness conditions reveal an optimal algorithm which involves JK thresholds that play a similar role as the 1/e-threshold in the optimal classical secretary algorithm. In particular, for the case K = 1, the J optimal thresholds have a nice "rational description". Our continuous LP analysis gives a very clear perspective on the problem, and the new insights inspire us to solve two related problems.
1. We settle the open problem whether algorithms based only on relative merits can achieve optimal ratio for matroid secretary problems. We show that, for online 2-item auction with random arriving bids (the K-uniform matroid problem with K = 2), an algorithm making decisions based only on relative merits cannot achieve the optimal ratio. This is in contrast with the folklore that, for online 1-item auction, no algorithm can have performance ratio strictly larger than 1/e, which is achievable by an algorithm that considers only relative merits.
2. We give a general transformation technique that takes any monotone algorithm (such as threshold algorithms) for the (K, K)-secretary problem, and constructs an algorithm for online bipartite K-matching with random arrival order that has at least the same performance guarantee.