TY - JOUR
A1 - Hoefer, Martin
A1 - Wilhelmi, Lisa
T1 - Packing returning secretaries
T2 - Networks
N2 - 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.
KW - coupon collector problem
KW - matching
KW - matroids, online algorithm
KW - packing problem
KW - secretary problem
Y1 - 2020
UR - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/57746
UR - https://nbn-resolving.org/urn:nbn:de:hebis:30:3-577467
SN - 1097-0037
VL - 2020
SP - 1
EP - 18
PB - Wiley
CY - New York, NY
ER -