Top

Published in:

2021 | OriginalPaper | Chapter

The Secretary Problem with Reservation Costs

Authors : Elisabet Burjons, Matthias Gehnen, Henri Lotze, Daniel Mock, Peter Rossmanith

Published in: Computing and Combinatorics

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We introduce two variants of the secretary problem, where a reservation fee can be paid to keep candidates on a short-list instead of rejecting them on the spot. In the first model, the fee has to be paid only once and keeps the reservation forever. In the second model, the fee has to be paid in every round as long as the reservation is kept. We analyze the competitive ratio for both variants and present optimal, relatively simple strategies.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Single-Pass Streaming Algorithms to Partition Graphs into Few Forests

next chapter Online Ride-Hitching in UAV Travelling

Albers, S., Ladewig, L.: New results for the \(k\)-secretary problem. In: 30th International Symposium on Algorithms and Computation, ISAAC. LIPIcs, vol. 149, pp. 18:1–18:19 (2019). https://doi.org/10.4230/LIPIcs.ISAAC.2019.18

Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX/RANDOM -2007. LNCS, vol. 4627, pp. 16–28. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74208-1_2CrossRef

Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Online auctions and generalized secretary problems. SIGecom Exch. 7(2), (2008). https://doi.org/10.1145/1399589.1399596

Bianchi, M.P., Böckenhauer, H.-J., Brülisauer, T., Komm, D., Palano, B.: Online minimum spanning tree with advice. Int. J. Found. Comput. Sci. 29(4), 505–527 (2018). https://doi.org/10.1142/S0129054118410034MathSciNetCrossRefMATH

Bianchi, M.P., Böckenhauer, H.-J., Hromkovič, J., Krug, S., Steffen, B.: On the advice complexity of the online \(L(2,1)\)-coloring problem on paths and cycles. Theor. Comput. Sci. 554, 22–39 (2014). https://doi.org/10.1016/j.tcs.2014.06.027MathSciNetCrossRefMATH

Böckenhauer, H.-J., Burjons, E., Hromkovič, J., Lotze, H., Rossmanith, P.: Online simple knapsack with reservation costs. In: 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021. LIPIcs, vol. 187, pp. 16:1–16:18 (2021). https://doi.org/10.4230/LIPIcs.STACS.2021.16

Böckenhauer, H.-J., Dobson, R., Krug, S., Steinhöfel, K.: On energy-efficient computations with advice. In: Xu, D., Du, D., Du, D. (eds.) COCOON 2015. LNCS, vol. 9198, pp. 747–758. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21398-9_58CrossRef

Böckenhauer, H.-J., Fuchs, J., Unger, W.: Exploring sparse graphs with advice (extended abstract). In: Epstein, L., Erlebach, T. (eds.) WAOA 2018. LNCS, vol. 11312, pp. 102–117. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-04693-4_7CrossRef

Böckenhauer, H.-J., Hromkovič, J., Komm, D., Královič, R., Rossmanith, P.: On the power of randomness versus advice in online computation. In: Bordihn, H., Kutrib, M., Truthe, B. (eds.) Languages Alive. LNCS, vol. 7300, pp. 30–43. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31644-9_2CrossRef

10.

Böckenhauer, H.-J., Hromkovič, J., Komm, D., Krug, S., Smula, J., Sprock, A.: The string guessing problem as a method to prove lower bounds on the advice complexity. Theor. Comput. Sci. 554, 95–108 (2014). https://doi.org/10.1016/j.tcs.2014.06.006MathSciNetCrossRefMATH

11.

Böckenhauer, H.-J., Hromkovič, J., Krug, S., Unger, W.: On the advice complexity of the online dominating set problem. Theor. Comput. Sci. 862, 81–96 (2021). https://doi.org/10.1016/j.tcs.2021.01.022MathSciNetCrossRefMATH

12.

Böckenhauer, H.-J., Komm, D., Královič, R., Královič, R.: On the advice complexity of the k-server problem. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6755, pp. 207–218. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22006-7_18CrossRefMATH

13.

Böckenhauer, H.-J., Komm, D., Královič, R., Královič, R., Mömke, T.: Online algorithms with advice: the tape model. Inf. Comput. 254, 59–83 (2017). https://doi.org/10.1016/j.ic.2017.03.001MathSciNetCrossRefMATH

14.

Böckenhauer, H.-J., Komm, D., Královič, R., Rossmanith, P.: The online knapsack problem: advice and randomization. Theor. Comput. Sci. 527, 61–72 (2014). https://doi.org/10.1016/j.tcs.2014.01.027MathSciNetCrossRefMATH

15.

Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)MATH

16.

Buchbinder, N., Jain, K., Singh, M.: Secretary problems via linear programming. Math. Oper. Res. 39(1), 190–206 (2014). https://doi.org/10.1287/moor.2013.0604MathSciNetCrossRefMATH

17.

Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006). https://doi.org/10.1017/CBO9780511546921CrossRefMATH

18.

Hubert Chan, T.-H., Chen, F., Jiang, S.H.-C.: 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: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4–6 January 2015, pp. 1169–1188. SIAM (2015). https://doi.org/10.1137/1.9781611973730.78

19.

Daniely, A., Mansour, Y.: Competitive ratio vs regret minimization: Achieving the best of both worlds. In: Algorithmic Learning Theory, ALT 2019, 22–24 March 2019, Chicago, Illinois, USA. Proceedings of Machine Learning Research, vol. 98, pp. 333–368. PMLR (2019)

20.

Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Sov. Math. 4, 627–629 (1963)MATH

21.

Kleinberg, R.D.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, 23–25 January 2005, pp. 630–631. SIAM (2005)

22.

Komm, D.: An Introduction to Online Computation - Determinism, Randomization, Advice. Texts in Theoretical Computer Science. An EATCS Series, Springer, Cham (2016). https://doi.org/10.1007/978-3-319-42749-2CrossRef

23.

Lindley, D.V.: Dynamic programming and decision theory. J. R. Stat. Soc. Ser. C (Appl. Stat.) 10(1), 39–51 (1961). http://www.jstor.org/stable/2985407

24.

Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985). https://doi.org/10.1145/2786.2793MathSciNetCrossRef

Title: The Secretary Problem with Reservation Costs
Authors: Elisabet Burjons
Matthias Gehnen
Henri Lotze
Daniel Mock
Peter Rossmanith
Publisher: Springer International Publishing
Book: Computing and Combinatorics
Print ISBN: 978-3-030-89542-6

Electronic ISBN: 978-3-030-89543-3

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-89543-3_46

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner