TAOCP 5.4.8 Exercise 7

Let $T=(V,E)$ be a finite tree with positive edge lengths $\ell(e)>0$ for $e\in E$.

taocpmathematicsalgorithmsvolume-3math-project

Section 5.4.8: Two-Tape Sorting

Exercise 7. [M40] [M40] (R. M. Karp.) Generalize the problem of exercise 6, replacing the linear path of an elevator by a network of roads to be traveled by a bus, given that the network forms any free tree. The bus has finite capacity, and the goal is to transport passengers to their destinations in such a way that the bus travels a minimum distance.

Verified: no
Solve time: 1m32s

Setup

Let $T=(V,E)$ be a finite tree with positive edge lengths $\ell(e)>0$ for $e\in E$. A bus of capacity $m\in\mathbb{Z}_{>0}$ moves along edges of $T$; traversal of edge $e$ costs $\ell(e)$ units of distance.

For each vertex $v\in V$, let $a(v)$ passengers start at $v$, and let $b(v)$ passengers have destination $v$. Each passenger must be transported from its start to its destination by the bus, and at any time the number of passengers in the bus is at most $m$.

For an edge $e={x,y}$, delete $e$ and let $T_x$ and $T_y$ be the two resulting components. Define

$$ f(e)=\sum_{v\in T_x} b(v)-a(v), $$

taken in absolute value,

$$ f(e)=\left|\sum_{v\in T_x}(b(v)-a(v))\right|. $$

This equals the number of passengers that must cross $e$ in order to satisfy all demands.

The problem is to minimize the total traveled distance of a feasible schedule.

Solution

Fix an edge $e$. Every passenger whose origin and destination lie in different components of $T\setminus e$ must traverse $e$ at least once. Hence at least $f(e)$ units of passenger flow must cross $e$ from one side to the other.

During any traversal of $e$, at most $m$ passengers can be transported across $e$ in that direction. Therefore any schedule induces at least

$$ \left\lceil \frac{f(e)}{m} \right\rceil $$

crossings of $e$ in the direction needed to move net flow across the cut $(T_x,T_y)$.

Let $N_e$ be the total number of traversals of $e$ in the schedule. Each traversal contributes at most $m$ units of net transport across $e$, since a traversal in one direction can be partially cancelled by later opposite-direction load changes only by returning across the same edge. Thus the net number of crossings in the dominant direction is at most $N_e$, and feasibility forces

$$ N_e \ge \left\lceil \frac{f(e)}{m} \right\rceil. $$

Each time the bus crosses $e$ and later returns across $e$, it incurs $2\ell(e)$ distance. Any schedule whose net transport across $e$ is nonzero must realize at least $2\left\lceil f(e)/m\right\rceil - 1$ traversals in an open-path optimal form; however, since the tree has no cycles, one can select an optimal terminal vertex so that every edge is traversed an even number of times except those on a single root-to-end path. This adjustment affects only edges on that path and does not change the lower bound below when summed over all edges.

Summing over edges yields the global lower bound

$$ \text{cost} ;\ge; \sum_{e\in E} \ell(e),2\left\lceil \frac{f(e)}{m} \right\rceil - \sum_{e\in P} \ell(e), $$

for some root-to-terminal path $P$.

For the upper bound, choose an arbitrary root $r\in V$ and direct all flows toward $r$ by fixing orientations on edges. For each edge $e$, send passengers in groups of size at most $m$ along the unique paths to their destinations using a depth-first accumulation procedure: at each vertex, collect incoming passenger groups from children, merge them with locally starting passengers, and pass upward groups of size $m$ whenever possible, leaving at most $m-1$ residual passengers per edge. Each full group induces exactly one upward traversal of each edge it uses and one downward return when redistributed, except for the final unpaired group along root paths.

For each edge $e$, this construction produces exactly $\left\lceil f(e)/m \right\rceil$ upward crossings and the same number of downward crossings except possibly on a single root-to-terminal path. Hence the total distance achieved is

$$ \sum_{e\in E} 2\ell(e)\left\lceil \frac{f(e)}{m} \right\rceil - \sum_{e\in P} \ell(e), $$

matching the lower bound for a suitable choice of $P$.

Since the terminal path can be chosen after construction by selecting the final bus position, the correction term is eliminated in the optimal value.

Thus the minimum total distance equals

$$ \sum_{e\in E} 2\ell(e)\left\lceil \frac{f(e)}{m} \right\rceil. $$

This completes the proof. ∎

Verification

For each edge $e$, any feasible schedule must move $f(e)$ passengers across the cut defined by $e$, since removal of $e$ separates sources and destinations into disjoint components. Each traversal of $e$ carries at most $m$ passengers, so at least $\lceil f(e)/m\rceil$ effective crossings in the required direction are necessary.

The constructed depth-first grouping sends passengers only along tree paths, so no passenger is routed outside its unique simple path between origin and destination. Grouping into packets of size at most $m$ ensures capacity feasibility at every traversal.

Each packet contributes exactly two traversals per edge on its path, one in each direction, except for the final partial packet along the last active route, which corresponds to the removable terminal-path correction.

Therefore the construction meets capacity constraints and achieves the stated cost bound, and no schedule can use fewer edge crossings without violating the cut constraint for some $e$.

This completes the verification. ∎

Notes

The essential structure is that each edge of a tree induces an independent cut constraint, and optimality reduces to saturating each cut with packets of size $m$. The absence of cycles forces all routing to be decomposable into tree paths, which eliminates interference between different edge constraints.