Fractional primal-dual ski rental: exact finite-$B$ competitive ratio

Setup and notation

The declaration takes two natural-number arguments, $B$ and $k$, and one hypothesis $0 < B$. There is no hypothesis relating $k$ and $B$: $k$ is an arbitrary natural number, including $0$ and values far exceeding $B$. Throughout, $B$ is silently coerced to a real number wherever it appears in arithmetic.

Fix the constant $c := c^{*}(B) = \bigl(1 + \tfrac{1}{B}\bigr)^{B} - 1$. The theorem instantiates every occurrence of the algorithm's free parameter at this single value; nothing is asserted for any other parameter value.

Define the real sequence $(x_j)_{j \in \mathbb{N}}$ by

$$x_0 = 0, \qquad x_{j+1} \;=\; \begin{cases} x_j\bigl(1 + \tfrac{1}{B}\bigr) + \dfrac{1}{c\,B}, & \text{if } x_j < 1 \quad (\textbf{strict}),\\[2mm] x_j, & \text{if } x_j \ge 1 .\end{cases}$$

The "else" branch freezes the value at whatever $x_j$ happens to be; it does not clip it to $1$. Define the companion sequence $z_j = 1 - x_j$ if $x_j < 1$, and $z_j = 0$ if $x_j \ge 1$; in particular $z_0 = 1$ always. Two further definitions are used verbatim: $\mathrm{primalCost}_B(x, z) = B x + \sum_{j<k} z_j$, and $\mathrm{offlineOpt}(B,k) = \min\{B, k\}$ — a definition, not characterized as any optimum. So the algorithm's cost is literally $\mathrm{ALG}(k) = B x_k + \sum_{j=0}^{k-1} z_j$: the final value $x_k$ multiplied by $B$, plus the $z$-values at indices $0,\dots,k-1$.

The conclusion is a conjunction of exactly three claims, all under the single hypothesis $0 < B$.

Component 1 — Monotonicity of the $x$-sequence

Asserts, with $\mathbb{N}$ and $\mathbb{R}$ carrying their usual orders:

$$\forall\, a, b \in \mathbb{N}, \quad a \le b \;\Longrightarrow\; x_a \le x_b .$$

This is a non-strict inequality (equality is permitted, and the frozen branch produces equalities). This component quantifies over all pairs of natural indices — the whole infinite sequence — and does not mention $k$ at all; for each $k$ the theorem simply restates the same $k$-independent claim.

Component 2 — Box feasibility at index $k$

Unfolds to the conjunction of three parts:

1. $0 \le x_k$ and $x_k \le 1$ — the single final iterate lies in the closed unit interval (both non-strict; note this is the same $x_k$ whose defining recursion only guards on $x_j < 1$).
2. For every index $j$ with $0 \le j \le k-1$: $0 \le z_j$ and $z_j \le 1$.
3. For every index $j$ with $0 \le j \le k-1$: $1 \le x_k + z_j$.

Part 3 pairs $z_j$ with $x_k$, the last iterate, and not with the contemporaneous $x_j$. All three parts are stated with non-strict inequalities. This component depends on $k$, both in the value $x_k$ and in the range of the quantifiers.

Component 3 — The cost inequality

$$B\,x_k \;+\; \sum_{j=0}^{k-1} z_j \;\;\le\;\; \left(1 + \frac{1}{\bigl(1+\tfrac1B\bigr)^{B} - 1}\right)\min\{B,\,k\} \;=\; \frac{\bigl(1+\tfrac1B\bigr)^{B}}{\bigl(1+\tfrac1B\bigr)^{B} - 1}\;\min\{B,\,k\}.$$

The multiplicative factor depends only on $B$ and not on $k$. The inequality is non-strict, oriented with the algorithm's cost on the left.

$k$-dependence summary

Component 1 is independent of $k$ (a statement about the entire sequence over $\mathbb{N}$). Components 2 and 3 depend on $k$. The competitive factor itself is independent of $k$ and depends on $B$ only.

Degenerate and edge cases

• $k = 0$. Both universally quantified parts of Component 2 are vacuous; Component 2 reduces to $0 \le x_0 \le 1$ with $x_0 = 0$. The sum in $\mathrm{ALG}(0)$ is empty, so Component 3 reads $0 \le \bigl(1 + 1/c^{*}(B)\bigr)\cdot\min\{B,0\}$, and since $B \ge 1$ the right side is $0$; the assertion at $k=0$ is $0 \le 0$.
• $k = B$. $\min\{B,k\} = B$, so the bound becomes $B\bigl(1 + 1/c^{*}(B)\bigr)$; the left side is $B x_B + \sum_{j<B} z_j$.
• $k \gg B$. $\min\{B,k\} = B$, so the right-hand side is constant in $k$, while the left-hand sum formally ranges over $k$ terms (each term with $x_j \ge 1$ being $0$). No hypothesis excludes this regime.
• $B = 1$. $c^{*}(1) = 1$, the factor is exactly $2$, the bound is $2\min\{1,k\}$, and the recursion gives $x_1 = 1$ so the guard fails from index $1$ onward.
• $B = 0$ is excluded by the hypothesis; consequently the reciprocals $1/B$, $1/(cB)$ are ordinary divisions rather than the $1/0 = 0$ junk value. For $B \ge 1$, $\bigl(1+\tfrac1B\bigr)^{B} \ge 2$, so $c^{*}(B) \ge 1$.
• Strictness of the guard. Every branch tests $x_j < 1$ strictly; at exactly $x_j = 1$ the "else" branches apply.
• Index coercion. The $z$-indices are $0,\dots,k-1$; index $k$ never appears among the $z$-terms, while the $x$-value used in Components 2 and 3 is exactly $x_k$.

What is not asserted

• No optimality or lower bound. Nothing says the factor is best possible, and no lower bound is proved against any algorithm, class of algorithms, or adversary.
• No duality content. No dual variables, no dual feasibility, no weak- or strong-duality statement, and no claim that $\min\{B,k\}$ is the optimum of any linear program — $\mathrm{offlineOpt}$ is only the definition $\min\{B,k\}$.
• No online information-constraint formalization. There is no formal model of an adversary or an input sequence, and no restriction stated that decisions at index $j$ depend only on the prefix; the "algorithm" is only the explicit recursion above.
• No claim about the sequence beyond the stated bounds: not that $x_B = 1$, not that $x_j$ reaches $1$ at any particular index, not that $x_j < 1$ for $j < B$, not that $z_j = 0$ for $j \ge B$, and no closed form.
• No per-time feasibility. Feasibility is asserted only for the pair $(x_k, z_j)$; no claim is made about $x_j + z_j \ge 1$ at intermediate times.
• No integrality or randomization. Only box-relaxed quantities appear; no integral solution, no rounding, no distribution, no expected-cost claim.
• No asymptotics. Nothing about $c^{*}(B) \to e - 1$ or $1 + 1/c^{*}(B) \to e/(e-1)$, nothing about monotonicity of the factor in $B$, not even the positivity $c^{*}(B) > 0$.
• No statement for $B = 0$, and no claim for parameter values other than $c = c^{*}(B)$.
• No tightness, uniqueness, or minimality of the cost, and no claim that $\mathrm{ALG}(k)$ is the minimum of $\mathrm{primalCost}$ over feasible points.