Packing returning secretaries. Issue 3 (26th November 2020)

• Record Type: Journal Article
• Authors: Hoefer, Martin; Wilhelmi, Lisa
• Is Part Of: Networks. Volume 77:Issue 3(2021)
• Page Start: 454
• Page End: 471
• Publication Date: 2020-11-26
• Subjects: coupon collector problem -- matching -- matroids -- online algorithm -- packing problem -- secretary problem; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22000
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: 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 2 n 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.