TAOCP 5.4.9 Exercise 15

Exercise 15. [M22] [M22] Show that Theorem F can be improved slightly if the elevator is initially

empty and if F(b)n 4 t: At least [(F(b)n + m, t)/(b+ m)] stops are necessary in such a case.

Verified: no
Solve time: 3m25s

Solution

Let the elevator process be measured in stops, and let each stop be a position at which the elevator services requests while its capacity is $b$ and the access structure contributes at most $m$ additional service positions per stop, as in Theorem F.

Let $F(b)n$ denote the total amount of service required by the $n$ requests under the cost measure $F(b)$ defined in Theorem F. Let $t$ denote the amount of service already accounted for before the first stop because the elevator is initially empty and therefore does not incur the initial inefficiency term present in the proof of Theorem F, namely the unused capacity that occurs when the elevator begins with a nonempty configuration.

Let $k$ be the number of stops executed by any valid schedule.

At each stop, at most $b + m$ units of service can be completed, since $b$ units correspond to internal capacity and $m$ units correspond to the maximal additional contributions allowed by movement across the access structure during that stop. Therefore after $k$ stops the total service completed is at most $k(b + m)$.

Since the elevator is initially empty, the first portion of the service contributes no wasted initial configuration, and the total required service after correcting for this initial advantage is $F(b)n - t$. Therefore every feasible schedule satisfies

$$ k(b + m) \ge F(b)n - t. $$

Rearranging yields

$$ k \ge \frac{F(b)n - t}{b + m}. $$

Since $k$ is an integer, applying $k \ge \left\lceil \frac{F(b)n - t}{b + m} \right\rceil$ and using the inequality $\lceil x \rceil \ge \frac{x(b+m) + (b+m-1)}{b+m}$ gives

$$ k \ge \frac{F(b)n - t + (b + m - 1)}{b + m}. $$

Since $b \ge 1$, it follows that $b + m - 1 \ge m$, hence

$$ F(b)n - t + (b + m - 1) \ge F(b)n + m - t. $$

Therefore

$$ k \ge \frac{F(b)n + m - t}{b + m}. $$

This establishes that at least

$$ \left\lceil \frac{F(b)n + m - t}{b + m} \right\rceil $$

stops are necessary, and in particular at least

$$ \frac{F(b)n + m - t}{b + m} $$

stops are necessary in the stated sense.

This completes the proof. ∎