Packing Returning Secretaries
share
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 accept 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 that can be combined with arbitrary approximation algorithms for the packing domain, even when the total value of candidates is a subadditive function. For bipartite matching, we obtain an algorithm with competitive ratio at least 0.5721 - o(1) for growing n, 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 (returned into the pool). We mainly focus on minimizing the expected number of postponements when computing an optimal solution. An expected number of Θ(n n) is always sufficient. For matroids, we show that the expected number can be reduced to O(r (n/r)), where r < n/2 is the minimum of the ranks of matroid and dual matroid. For bipartite matching, we show a bound of O(r n), where r is the size of the optimum matching. For general packing, we show a lower bound of Ω(n n), even when the size of the optimum is r = Θ( n).
READ FULL TEXT