CoChat

Competitive Algorithms for an Online Rent or Buy Problem with Variable Demand

Open access
Kodialam, Rohan · 2014 · SIAM Undergraduate Research Online

The DOI matches its Crossref record; 9 of the 9 references it cites were found in a registry or an index; none of the 1 sources its claims cite is checked for support yet.

Abstract

We consider a generalization of the classical Ski Rental Problem motivated by applications in cloud computing.We develop deterministic and probabilistic online algorithms for rent/buy decision problems with time-varying demand.We show that these algorithms have competitive ratios of 2 and 1.582 respectively.We also further establish the optimality of these algorithms.

Overview

CoChat Summary

TL;DR

The paper generalizes the ski-rental problem to online rent-or-buy decisions with time-varying demand, motivated by cloud bursting. It gives a deterministic online algorithm with competitive ratio \(2 - 1/b\) and a randomized algorithm with expected competitive ratio \(e/(e-1)\), and proves both are optimal.

Key findings

  • A deterministic online algorithm \(A_{on}\) achieves competitive ratio \(2 - 1/b\), and no deterministic online algorithm can do better.
  • A probabilistic online algorithm \(A_{prob}\) achieves expected competitive ratio \(e/(e-1)\), approximately 1.582, and no probabilistic online algorithm can do better.
  • In the example with \(b=3\) and demand vector \(\{3,5,2,4,8,1,6\}\), the offline optimum cost is 19, the deterministic online cost is 29 (ratio \(\approx 1.526\)), and the probabilistic expected cost is \(\approx 26.684\) (ratio \(\approx 1.404\)).
  • The offline optimum is characterized by buying \(h^n_b\) items initially and renting only when \(d_i > h^n_b\), with cost \(\sum_{i \in S^n_b} d_i + (b-1)h^n_b\).

Methods

  • The problem is formalized as an online rent/buy problem where demand \(d_i \ge 0\) arrives once per day, renting costs \(r=1\) per unit per day, and buying costs \(b \ge r\) per unit for all future days.
  • The offline problem is solved via a linear program and its dual; the online deterministic algorithm buys up to the \(b\)-th highest demand seen so far, and the probabilistic algorithm randomizes over buying up to the \(a\)-th highest demand for \(a \in \{1,\dots,b\}\).
  • Competitive analysis compares online cost to optimal offline cost over all demand vectors; the optimal randomized distribution is derived by equalizing coefficients \(c_a = b p_a + \sum_{j=a+1}^b p_j\), yielding a geometric distribution with ratio \(b/(b-1)\).

Limitations

  • The paper states that it is currently studying variants under more general cost models and realistic constraints.
  • The paper states that the model abstracts several practical considerations of real-world cloud bursting and that it assumes \(r=1\) and integral \(b\) for convenience, noting results extend by setting \(b\) to \(\lceil b \rceil\).
  • Evident from the text: the analysis is worst-case over adversarial demand sequences, assumes demands arrive once per time period, and does not know the number of periods \(n\) in advance.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1137/14s013032

Cites

9 of 9 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

0 Valid · 0 Not valid · 2 Not checked · 17 Own results and interpretations

8 more claims

Create a free account to see all 19 claims and every source verdict.

See all claims — free account
  • Probably not a substantial claim. 5
  • It may state two separate claims as one. 1

Create a free account to see these claims.

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

2 of 2

Citations

Cites

Cited by

See all 4

Metadata

Authors
Kodialam, R.
Affiliations
Brooklyn Technical High School (US)
Corresponding author
Kodialam, Rohan
Venue
SIAM Undergraduate Research Online
Published
2014
Volume
7
ISSN
2327-7807 (ISSN-L)
OpenAlex
W2315956051
Cited by
4
References
9
Citations by year
2024: 1 · 2022: 1 · 2019: 1 · 2018: 1
FWCI
0.00
Type
journal article
Language
en
Open access
Locations
SIAM Undergraduate Research Online (publishedVersion)
Topics
  • Physical Sciences › Mathematics › Theoretical Computer Science › Optimization and Search Problems
  • Physical Sciences › Mathematics › Theoretical Computer Science › Algorithms and Data Compression
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
Keywords
ski rental problem, online algorithms, competitive ratio, time-varying demand, cloud computing, randomized algorithms, deterministic algorithms, algorithm optimality

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-10-10, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-10-10 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.