Document Open Access Logo

Packing Returning Secretaries

Authors Martin Hoefer, Lisa Wilhelmi

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.65.pdf
  • Filesize: 462 kB
  • 12 pages

Document Identifiers

Author Details

Martin Hoefer
  • Goethe University Frankfurt/Main, Germany
Lisa Wilhelmi
  • Goethe University Frankfurt/Main, Germany

Funding

Supported by a grant from the German-Israeli Foundation for Scientific Research and Development (GIF).

Cite As Get BibTex

Martin Hoefer and Lisa Wilhelmi. Packing Returning Secretaries. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 65:1-65:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ISAAC.2018.65

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 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 Theta(n log n) is always sufficient. For matroids, we show that the expected number can be reduced to O(r log (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 log n), where r is the size of the optimum matching. For general packing, we show a lower bound of Omega(n log log n), even when the size of the optimum is r = Theta(log n).

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Secretary Problem
  • Coupon Collector Problem
  • Matroids

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. A Knapsack Secretary Problem with Applications. In Proc. 10th Workshop Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 16-28, 2007. Google Scholar
  2. Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert Kleinberg. Online Auctions and Generalized Secretary Problems. SIGecom Exchanges, 7(2), 2008. Google Scholar
  3. Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. 18th Symp. Discrete Algorithms (SODA), pages 434-443, 2007. Google Scholar
  4. Arnon Boneh and Micha Hofri. The coupon-collector problem revisited - a survey of engineering problems and computational methods. Comm. Stat. Stoch. Models, 13(1):39-66, 1997. Google Scholar
  5. Ning Chen, Martin Hoefer, Marvin Künnemann, Chengyu Lin, and Peihan Miao. Secretary Markets with Local Information. In Proc. 42nd Intl. Coll. Automata, Languages &Programming (ICALP), volume 2, pages 552-563, 2015. Google Scholar
  6. Michael Dinitz. Recent advances on the matroid secretary problem. SIGACT News, 44(2):126-142, 2013. Google Scholar
  7. Uriel Feige. On Maximizing Welfare When Utility Functions Are Subadditive. SIAM J. Comput., 39(1):122-142, 2009. Google Scholar
  8. Moran Feldman, Ola Svensson, and Rico Zenklusen. A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem. Math. Oper. Res., 43(2):638-650, 2018. Google Scholar
  9. Moran Feldman and Rico Zenklusen. The Submodular Secretary Problem Goes Linear. SIAM J. Comput., 47(2):330-366, 2018. Google Scholar
  10. Thomas Ferguson. Who Solved the Secretary Problem? Statistical Science, 4(3):282-289, 1989. Google Scholar
  11. Amos Fiat, Ilia Gorelik, Haim Kaplan, and Slava Novgorodov. The Temp Secretary Problem. In Proc. 23rd European Symp. Algorithms (ESA), pages 631-642, 2015. Google Scholar
  12. Philippe Flajolet, Danièle Gardy, and Loÿs Thimonier. Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-Organizing Search. Disc. Appl. Math., 39(3):207-229, 1992. Google Scholar
  13. Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking. Online Independent Set Beyond the Worst-Case: Secretaries, Prophets and Periods. In Proc. 41st Intl. Coll. Automata, Languages &Programming (ICALP), volume 2, pages 508-519, 2014. Google Scholar
  14. MohammadTaghi Hajiaghayi, Robert Kleinberg, and David Parkes. Adaptive limited-supply online auctions. In Proc. 5th Conf. Electronic Commerce (EC), pages 71-80, 2004. Google Scholar
  15. Martin Hoefer and Bojana Kodric. Combinatorial Secretary Problems with Ordinal Information. In Proc. 44th Intl. Coll. Automata, Languages &Programming (ICALP), pages 133:1-133:14, 2017. Google Scholar
  16. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions. In Proc. 21st European Symp. Algorithms (ESA), pages 589-600, 2013. Google Scholar
  17. Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking. Primal Beats Dual on Online Packing LPs in the Random-Order Model. In Proc. 46th Symp. Theory of Comput. (STOC), pages 303-312, 2014. Google Scholar
  18. Thomas Kesselheim and Andreas Tönnis. Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints. In Proc. 20th Workshop Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 16:1-16:22, 2017. Google Scholar
  19. John Kobza, Sheldon Jacobson, and Diane Vaughan. A Survey of the Coupon Collector’s Problem with Random Sample Sizes. Methodol. Comput. Appl. Probab., 9:573-584, 2007. Google Scholar
  20. Nitish Korula and Martin Pál. Algorithms for Secretary Problems on Graphs and Hypergraphs. In Proc. 36th Intl. Coll. Automata, Languages &Programming (ICALP), pages 508-520, 2009. Google Scholar
  21. Oded Lachish. O(log log Rank)-Competitive Ratio for the Matroid Secretary Problem. In Proc. 55th Symp. Foundations of Comput. Sci. (FOCS), pages 326-335, 2014. Google Scholar
  22. Marco Molinaro and R. Ravi. Geometry of Online Packing Linear Programs. Math. Oper. Res., 39(1):46-59, 2014. Google Scholar
  23. Aviad Rubinstein. Beyond matroids: secretary problem and prophet inequality with general constraints. In Proc. 48th Symp. Theory of Comput. (STOC), pages 324-332, 2016. Google Scholar
  24. José Soto, Abner Turkieltaub, and Victor Verdugo. Strong Algorithms for the Ordinal Matroid Secretary Problem. In Proc. 29th Symp. Discrete Algorithms (SODA), pages 715-734, 2018. Google Scholar
  25. Shai Vardi. The Returning Secretary. In Proc. 32nd Symp. Theoret. Aspects of Comput. Sci. (STACS), pages 716-729, 2015. Full version CoRR abs/1404.0614. URL: http://arxiv.org/abs/1404.0614.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact