{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T15:42:48Z","timestamp":1740152568650,"version":"3.37.3"},"reference-count":28,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T00:00:00Z","timestamp":1600819200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1755254"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"Many sharing-economy platforms operate as follows. Owners list the availability of resources, prices, and contract-length limits. Customers propose contract start times and lengths. The owners decide immediately whether to accept or decline each proposal, even if the contract is for a future date. Accepted proposals generate revenue. Declined proposals are lost. At any decision epoch, the owner has no information regarding future proposals. The owner seeks easy-to-implement algorithms that achieve the best competitive ratio (CR). We first derive a lower bound on the CR of any algorithm. We then analyze CRs of all intuitive \u201cgreedy\u201d algorithms. We propose two new algorithms that have significantly better CRs than that of any greedy algorithm for certain parameter-value ranges. The key idea behind these algorithms is that owners may reserve some amount of capacity for late-arriving higher-value proposals in an attempt to improve revenue. Our contribution lies in operationalizing this idea with the help of algorithms that utilize thresholds. Moreover, we show that if non-optimal thresholds are chosen, then those may lead to poor CRs. We provide a rigorous method by which an owner can decide the best approach in their context by analyzing the CRs of greedy algorithms and those proposed by us.<\/jats:p>","DOI":"10.3390\/a13100241","type":"journal-article","created":{"date-parts":[[2020,9,23]],"date-time":"2020-09-23T13:28:08Z","timestamp":1600867688000},"page":"241","source":"Crossref","is-referenced-by-count":4,"title":["The Online Reservation Problem"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0899-4460","authenticated-orcid":false,"given":"Shashank","family":"Goyal","sequence":"first","affiliation":[{"name":"Department of Industrial & Systems Engineering, University of Minnesota\u2014Twin Cities, Minneapolis, MN 55455, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4716-2504","authenticated-orcid":false,"given":"Diwakar","family":"Gupta","sequence":"additional","affiliation":[{"name":"McCombs School of Business, University of Texas at Austin, Austin, TX 78705, USA"}]}],"member":"1968","published-online":{"date-parts":[[2020,9,23]]},"reference":[{"key":"ref_1","unstructured":"Fraiberger, S.P., and Sundararajan, A. (2020, July 01). Peer-to-Peer Rental Markets in the Sharing Economy. NYU Stern School of Business Research Paper. Available online: https:\/\/ssrn.com\/abstract=2574337."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"2047","DOI":"10.1002\/asi.23552","article-title":"The sharing economy: Why people participate in collaborative consumption","volume":"67","author":"Hamari","year":"2016","journal-title":"J. Assoc. Inf. Sci. Technol."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.ecolecon.2015.11.027","article-title":"The sharing economy: A pathway to sustainability or a nightmarish form of neoliberal capitalism?","volume":"121","author":"Martin","year":"2016","journal-title":"Ecol. Econ."},{"key":"ref_4","unstructured":"AngelList (2019, July 01). Sharing Economy Startups. Available online: https:\/\/angel.co\/sharing-economy-4."},{"key":"ref_5","unstructured":"Zilok (2018, January 01). Rental Wedding Gown. Available online: us.zilok.com\/rental\/119802-wedding-gown.html."},{"key":"ref_6","unstructured":"DCA (2012). California Tenants: A Guide to Residential Tenants\u2019 and Landlords\u2019 Rights and Responsibilities, California Department of Consumer Affairs."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1002\/nav.20231","article-title":"Interval scheduling: A survey","volume":"54","author":"Kolen","year":"2007","journal-title":"Naval Res. Logist. (NRL)"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Ma, W., and Simchi-Levi, D. (2020). Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res.","DOI":"10.1287\/opre.2019.1957"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1014","DOI":"10.1287\/opre.2013.1188","article-title":"Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms","volume":"61","author":"Buchbinder","year":"2013","journal-title":"Oper. Res."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1080\/0740817X.2015.1078016","article-title":"Reserve driver scheduling","volume":"48","author":"Gupta","year":"2016","journal-title":"IIE Trans."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Azar, Y., Boyar, J., Favrholdt, L.M., Larsen, K.S., and Nielsen, M.N. (2000). Fair versus Unrestricted Bin Packing. Algorithm Theory\u2014SWAT 2000, Springer.","DOI":"10.1007\/3-540-44985-X_18"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"836","DOI":"10.1111\/poms.12672","article-title":"Revenue management of reusable resources with advanced reservations","volume":"26","author":"Chen","year":"2017","journal-title":"Prod. Oper. Manag."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1017\/apr.2015.4","article-title":"Queues with advanced reservations: An infinite-server proxy for the bookings diary","volume":"48","author":"Maillardet","year":"2016","journal-title":"Adv. Appl. Probab."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1080\/15326349.2014.900388","article-title":"Blocking probabilities in Erlang loss queues with advance reservation","volume":"30","author":"Litvak","year":"2014","journal-title":"Stoch. Models"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1023\/B:JOSH.0000031423.39762.d3","article-title":"An Improved Randomized On-Line Algorithm for a Weighted Interval Selection Problem","volume":"7","author":"Miyazawa","year":"2004","journal-title":"J. Sched."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/S0167-6377(98)00019-4","article-title":"Randomized online interval scheduling","volume":"22","author":"Seiden","year":"1998","journal-title":"Oper. Res. Lett."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0166-218X(95)00112-5","article-title":"Note on scheduling intervals on-line","volume":"58","author":"Faigle","year":"1995","journal-title":"Discret. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/s10878-007-9131-z","article-title":"Online interval scheduling: Randomized and multiprocessor cases","volume":"16","author":"Fung","year":"2008","journal-title":"J. Comb. Optim."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1137\/S0097539792236882","article-title":"Dover: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems","volume":"24","author":"Koren","year":"1995","journal-title":"SIAM J. Comput."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/BF00365406","article-title":"On the competitiveness of on-line real-time task scheduling","volume":"4","author":"Baruah","year":"1992","journal-title":"Real Time Syst."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","article-title":"The Design of Competitive Online Algorithms via a Primal\u2013Dual Approach","volume":"3","author":"Buchbinder","year":"2009","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/PL00009286","article-title":"The Seat Reservation Problem","volume":"25","author":"Boyar","year":"1999","journal-title":"Algorithmica"},{"key":"ref_23","unstructured":"Lipton, R.J., and Tomkins, A. (1994, January 23\u201325). Online Interval Scheduling. Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1006\/jcss.2001.1799","article-title":"Competitive On-line Scheduling of Continuous-Media Streams","volume":"64","author":"Garofalakis","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/BF02309339","article-title":"Randomized online algorithms for maximizing busy time interval scheduling","volume":"56","author":"Faigle","year":"1996","journal-title":"Computing"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1287\/opre.1080.0654","article-title":"Toward Robust Revenue Management: Competitive Analysis of Online Booking","volume":"57","author":"Ball","year":"2009","journal-title":"Oper. Res."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C. (2, January 31). Probabilistic computations: Toward a unified measure of complexity. Proceedings of the 18th Annual Symposium on Foundations of Computer Science (SFCS 1977), Providence, RI, USA.","DOI":"10.1109\/SFCS.1977.24"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Goyal, S. (2018). Essays on The Online Multiple Knapsack Problem & The Online Reservation Problem. [Ph.D. Thesis, University of Minnesota].","DOI":"10.2139\/ssrn.3137277"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/241\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T14:44:21Z","timestamp":1720017861000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/10\/241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,23]]},"references-count":28,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2020,10]]}},"alternative-id":["a13100241"],"URL":"https:\/\/doi.org\/10.3390\/a13100241","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2020,9,23]]}}}