Document Open Access Logo

New Results for the k-Secretary Problem

Authors Susanne Albers, Leon Ladewig

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.18.pdf
  • Filesize: 0.58 MB
  • 19 pages

Document Identifiers

Author Details

Susanne Albers
  • Department of Informatics, Technical University of Munich, Germany
Leon Ladewig
  • Department of Informatics, Technical University of Munich, Germany

Funding

Work supported by the European Research Council, Grant Agreement No. 691672.

Cite As Get BibTex

Susanne Albers and Leon Ladewig. New Results for the k-Secretary Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ISAAC.2019.18

Abstract

Suppose that n numbers arrive online in random order and the goal is to select k of them such that the expected sum of the selected items is maximized. The decision for any item is irrevocable and must be made on arrival without knowing future items. This problem is known as the k-secretary problem, which includes the classical secretary problem with the special case k=1. It is well-known that the latter problem can be solved by a simple algorithm of competitive ratio 1/e which is asymptotically optimal. When k is small, only for k=2 does there exist an algorithm beating the threshold of 1/e [Chan et al. SODA 2015]. The algorithm relies on an involved selection policy. Moreover, there exist results when k is large [Kleinberg SODA 2005].
In this paper we present results for the k-secretary problem, considering the interesting and relevant case that k is small. We focus on simple selection algorithms, accompanied by combinatorial analyses. As a main contribution we propose a natural deterministic algorithm designed to have competitive ratios strictly greater than 1/e for small k >= 2. This algorithm is hardly more complex than the elegant strategy for the classical secretary problem, optimal for k=1, and works for all k >= 1. We explicitly compute its competitive ratios for 2 <= k <= 100, ranging from 0.41 for k=2 to 0.75 for k=100. Moreover, we show that an algorithm proposed by Babaioff et al. [APPROX 2007] has a competitive ratio of 0.4168 for k=2, implying that the previous analysis was not tight. Our analysis reveals a surprising combinatorial property of this algorithm, which might be helpful for a tight analysis of this algorithm for general k.

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
Keywords
  • Online algorithms
  • secretary problem
  • random order model

Metrics

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

References

  1. S. Agrawal, Z. Wang, and Y. Ye. A Dynamic Near-Optimal Algorithm for Online Linear Programming. Operations Research, 62(4):876-890, 2014. Google Scholar
  2. M. Ajtai, N. Megiddo, and O. Waarts. Improved algorithms and analysis for secretary problems and generalizations. SIAM Journal on Discrete Mathematics, 14(1):1-27, 2001. Google Scholar
  3. M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. A Knapsack Secretary Problem with Applications. In Proc. 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 11th International Workshop on Randomization and Computation (APPROX/RANDOM), pages 16-28, 2007. Google Scholar
  4. M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. Online auctions and generalized secretary problems. SIGecom Exchanges, 7(2), 2008. Google Scholar
  5. M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. Matroid Secretary Problems. Journal of the ACM (JACM), 65(6):35:1-35:26, 2018. Google Scholar
  6. M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, secretary problems, and online mechanisms. In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 434-443, 2007. Google Scholar
  7. B. Bahmani, A. Mehta, and R. Motwani. A 1.43-Competitive Online Graph Edge Coloring Algorithm in the Random Order Arrival Model. In Proc. 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 31-39, 2010. Google Scholar
  8. N. Buchbinder, K. Jain, and M. Singh. Secretary Problems via Linear Programming. Mathematics of Operations Research, 39(1):190-206, 2014. Google Scholar
  9. T.-H. H. Chan, F. Chen, and S. H.-C. Jiang. Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1169-1188, 2015. Google Scholar
  10. E. B Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics, 4:627-629, 1963. Google Scholar
  11. M. Feldman, O. Svensson, and R. Zenklusen. A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem. In Proc. 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1189-1201, 2015. Google Scholar
  12. M. Feldman, O. Svensson, and R. Zenklusen. A Framework for the Secretary Problem on the Intersection of Matroids. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 735-752, 2018. Google Scholar
  13. T. S. Ferguson. Who Solved the Secretary Problem? Statistical Science, 4(3):282-289, 1989. Google Scholar
  14. P.R. Freeman. The secretary problem and its extensions: A review. International Statistical Review/Revue Internationale de Statistique, pages 189-206, 1983. Google Scholar
  15. O. Göbel, T. Kesselheim, and A. Tönnis. Online Appointment Scheduling in the Random Order Model. In Proc. 23rd Annual European Symposium on Algorithms (ESA), pages 680-692, 2015. Google Scholar
  16. R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete mathematics - a foundation for computer science (2. ed.). Addison-Wesley, 1994. Google Scholar
  17. M. Hoefer and B. Kodric. Combinatorial Secretary Problems with Ordinal Information. In 44th International Colloquium on Automata, Languages, and Programming (ICALP), pages 133:1-133:14, 2017. Google Scholar
  18. C. Kenyon. Best-Fit Bin-Packing with Random Order. In Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 359-364, 1996. Google Scholar
  19. T. Kesselheim, K. Radke, A. Tönnis, and B. Vöcking. Primal beats dual on online packing LPs in the random-order model. In Proc. 46th Annual ACM Symposium on Theory of Computing (STOC), pages 303-312, 2014. Google Scholar
  20. T. Kesselheim and A. Tönnis. Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints. In Proc. 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 21st International Workshop on Randomization and Computation (APPROX/RANDOM), pages 16:1-16:22, 2017. Google Scholar
  21. R. D. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 630-631, 2005. Google Scholar
  22. O. Lachish. O(log log Rank) Competitive Ratio for the Matroid Secretary Problem. In Proc. 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 326-335, 2014. Google Scholar
  23. D. V Lindley. Dynamic programming and decision theory. Applied Statistics, pages 39-51, 1961. Google Scholar
  24. M. Mahdian and Q. Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In Proc. 43rd ACM Symposium on Theory of Computing (STOC), pages 597-606, 2011. Google Scholar
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