Secretary Problems: Weights and Discounts

Conference object English OPEN
Babaioff, M.; Dinitz, M.; Gupta, Anupam; Immorlica, Nicole Simone; Talwar, K.;
(2009)
  • Publisher: ACM-SIAM

textabstractThe classical secretary problem studies the problem of selecting online an element (a “secretary”) with maximum value in a randomly ordered sequence. The difficulty lies in the fact that an element must be either selected or discarded upon its arrival, and t... View more
  • References (16)
    16 references, page 1 of 2

    [1] M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. A knapsack secretary problem with applications. In APPROX '07, 2007.

    [2] Moshe Babaioff, Nicole Immorlica, and Robert Kleinberg. Matroids, secretary problems, and online mechanisms. In SODA '07, pages 434-443, 2007.

    [3] Cyrus Derman, Gerald J. Lieberman, and Sheldon M. Ross. A sequential stochastic assignment problem. Management Sci., 18:349-355, 1971.

    [4] N. Dimitrov and C. G. Plaxton. Competitive weighted matching in transversal matroids. In Proc. 35th Intl. Colloq. on Automata, Languages and Programming (ICALP 2008), 2008.

    [5] E. B. Dynkin. Optimal choice of the stopping moment of a Markov process. Dokl. Akad. Nauk SSSR, 150:238-240, 1963.

    [6] T.S. Ferguson. Who solved the secretary problem? Statistical Science, 4:282-296, 1989.

    [7] P. R. Freeman. The secretary problem and its extensions: a review. Internat. Statist. Rev., 51(2):189-206, 1983.

    [8] A. Gershkov and B. Moldovanu. The dynamic assignment of heterogenous objects: A mechanism design approach. Technical report, University of Bonn, 2007.

    [9] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and David C. Parkes. Adaptive limited-supply online auctions. In EC '04, pages 71-80, 2004.

    [10] Robert Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In 16th SODA, pages 630- 631. ACM, 2005.

  • Metrics
    No metrics available
Share - Bookmark