Packing returning secretaries
- 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.
Author: | Martin HoeferORCiDGND, Lisa Wilhelmi |
---|---|
URN: | urn:nbn:de:hebis:30:3-577467 |
DOI: | https://doi.org/10.1002/net.22000 |
ISSN: | 1097-0037 |
Parent Title (German): | Networks |
Publisher: | Wiley |
Place of publication: | New York, NY |
Document Type: | Article |
Language: | English |
Date of Publication (online): | 2020/11/16 |
Date of first Publication: | 2020/11/26 |
Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Release Date: | 2021/02/18 |
Tag: | coupon collector problem; matching; matroids, online algorithm; packing problem; secretary problem |
Volume: | 2020 |
Page Number: | 18 |
First Page: | 1 |
Last Page: | 18 |
HeBIS-PPN: | 476999383 |
Institutes: | Informatik und Mathematik / Informatik |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Sammlungen: | Universitätspublikationen |
Licence (German): | Creative Commons - Namensnennung 4.0 |