Packing returning secretaries
Packing returning secretaries
复制标题
包装返回的秘书
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Lisa Wilhelmi
中科院分区：
文献类型：
--
作者：
M. Hoefer;Lisa Wilhelmi
我们研究了n个候选者随时间以随机顺序到达的组合包装域中的带回报的在线秘书问题。目标是确定具有最大总价值的候选对象的可行包装。在第一个变种中，每个候选人正好到达两次。所有2n次到达都是按随机顺序进行的。我们提出了一个简单的0.5-竞争算法。对于在线二部匹配问题，我们得到了一个比率至少为0.5721 − o(1)的算法，以及一个比率至少为0.5459的n ≥ 1的算法。我们将所有的算法和比率推广到每个候选者k个 ≥ 2到达。在第二个变种中，有一批尚未决定的候选人。在每一轮中，从池中随机选出一名候选人。候选人到达后，可以决定(接受/拒绝)或推迟。在计算最优解时，我们将重点放在最小化预期延迟次数上。期望的日志数量(nΘ n)始终足够。对于二部匹配，我们可以证明O(r n)的紧界，其中r是最优匹配的大小。对于拟阵，我们可以进一步改进到O(r‘ (n/r’))的紧界，其中r‘是拟阵和对偶拟阵的最小秩.
We study online secretary problems with returns in combinatorial packing domains with n candidates that arrive sequentially over time in random order. The goal is to determine a feasible packing of candidates of maximum total value. In the first variant, each candidate arrives exactly twice. All 2n arrivals occur in random order. We propose a simple 0.5‐competitive algorithm. For the online bipartite matching problem, we obtain an algorithm with ratio at least 0.5721 − o(1), and an algorithm with ratio at least 0.5459 for all n ≥ 1. We extend all algorithms and ratios to k ≥ 2 arrivals per candidate. In the second variant, there is a pool of undecided candidates. In each round, a random candidate from the pool arrives. Upon arrival a candidate can be either decided (accept/reject) or postponed. We focus on minimizing the expected number of postponements when computing an optimal solution. An expected number of Θ(n log n) is always sufficient. For bipartite matching, we can show a tight bound of O(r log n), where r is the size of the optimum matching. For matroids, we can improve this further to a tight bound of O(r′ log(n/r′)), where r′ is the minimum rank of the matroid and the dual matroid.