TAOCP 7.2.2.1 Exercise 249

Let the costs be revealed as a sequence $x_1, x_2, \ldots, x_{dt}$, where $\{x_1,\ldots,x_{dt}\} = \{c_1,\ldots,c_{dt}\}$ and each $x_t \ge 0$.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 249. [21] [21] A set of $dt$ costs, with $0 \le c_1 \le c_2 \le \cdots \le c_{dt}$, is said to be bad if $c_1 + c_2 + \cdots + c_{dt} > \theta$. Design an "online algorithm" that identifies a bad set as quickly as possible, when the costs are learned one by one in arbitrary order.

For example, suppose $d = 6$, $k = 2$, and $\theta = 16$. If costs appear in the order $(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8)$, your algorithm should stop after seeing the 2.

Verified: no
Solve time: 2m16s

Solution

Let the costs be revealed as a sequence $x_1, x_2, \ldots, x_{dt}$, where ${x_1,\ldots,x_{dt}} = {c_1,\ldots,c_{dt}}$ and each $x_t \ge 0$. Let $S_t = \sum_{s=1}^t x_s$.

An online algorithm maintains $S_t$ and halts at the first index $t$ such that $S_t > \theta$, declaring the set bad. If no such $t$ exists, the algorithm continues until all $dt$ costs have been seen, and then checks whether $S_{dt} > \theta$.

Correctness follows from the fact that all costs are nonnegative. If the algorithm halts at time $t$ with $S_t > \theta$, then $$ \sum_{i=1}^{dt} x_i \ge S_t > \theta, $$ since all remaining unseen terms are at least $0$, so the full sum exceeds $\theta$ and the set is bad.

Conversely, if the full set is bad, then $\sum_{i=1}^{dt} x_i > \theta$. Since $S_t$ is nondecreasing in $t$, there exists a least $t$ such that $S_t > \theta$, and the algorithm halts at that moment.

To show optimality in the online sense, suppose an algorithm halts at time $t$ with $S_t \le \theta$. At that moment, the remaining costs are unknown but each lies in $[0,\infty)$. There exists a completion of the instance in which all remaining costs are $0$, yielding total sum exactly $S_t \le \theta$, and there also exists a completion in which sufficiently large remaining costs make the total exceed $\theta$. Therefore no decision is forced before $S_t > \theta$ is observed, since both outcomes remain consistent with the observed prefix.

Thus any correct online algorithm cannot certify badness earlier than the first time the partial sum exceeds $\theta$, since prior to that point both bad and not-bad completions remain possible.

Therefore the earliest possible identification is achieved by stopping exactly when $S_t > \theta$.

This completes the proof. ∎