On the best possible competitive ratio for the multislope ski-rental problem

Hiroshi Fujiwara (), Takuma Kitano and Toshihiro Fujito
Additional contact information
Hiroshi Fujiwara: Shinshu University
Takuma Kitano: Denso Create Inc.
Toshihiro Fujito: Toyohashi University of Technology

Journal of Combinatorial Optimization, 2016, vol. 31, issue 2, No 2, 463-490

Abstract: Abstract The multislope ski-rental problem is an extension of the classical ski-rental problem, where the player has several lease options besides the pure rent and buy options. In this problem the hardness of an instance, which is the setting of options, significantly affects the player’s performance. There is an algorithm that for a given instance, computes the best possible strategy. However, the output is given as numerical values and therefore the relational nature between an instance and the best possible performance for it has not been known. In this paper we prove that even for the easiest instance, a competitive ratio smaller than $$e/(e - 1) \approx 1.58$$ e / ( e - 1 ) ≈ 1.58 cannot be achieved. More precisely, a tight lower bound on the best possible performance is obtained in a closed form parametrized by the number of options. Furthermore, we establish a matching upper and lower bound on the competitive ratio each for the 3-option and 4-option problems.

Keywords: Online algorithm; Competitive analysis; Online optimization; Ski-rental problem; Mathematical programming (search for similar items in EconPapers)
Date: 2016
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-014-9762-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:31:y:2016:i:2:d:10.1007_s10878-014-9762-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-014-9762-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().