TAOCP 7.1.1 Exercise 82

The previous argument fails because it incorrectly assumes separability of the objective and performs illegal local substitutions.

taocpmathematicsalgorithmsvolume-4medium

Section 7.1.1: Boolean Basics

Exercise 82. [25] (Incremental changes in service.) Given a sequence of vertices $(u_0, v_1, \ldots, v_t)$ in a graph $G$, consider the problem of finding another sequence $(u_0, u_1, \ldots, u_t)$ for which $u_0 = u_0$ and the sum

$$d(u_0, u_1) + d(u_1, u_2) + \cdots + d(u_{t-1}, u_t) + d(u_t, v_1) + d(u_1, v_2) + \cdots + d(u_t, v_t)$$

is minimized, where $d(u, v)$ denotes the distance from $u$ to $v$. (Each $v_k$ can be regarded as a request for a resource needed at that vertex; a server moves to $u_k$ as those requests are handled in sequence.) Prove that if $G$ is a median graph, we get an optimum solution by choosing $u_k = (u_{k-1} r_k u_{k+1})$ for $0 < k < t$, and $u_t = v_t$.

Verified: no
Solve time: 4m20s

Corrected solution

The previous argument fails because it incorrectly assumes separability of the objective and performs illegal local substitutions. We restart from a correct decomposition of the cost and use a valid local-to-global optimality argument based on the structure of median graphs.

1. Correct form of the objective and dependencies

The objective is

$$ F(u_1,\dots,u_t) = \sum_{k=1}^{t} d(u_{k-1},u_k)

  • d(u_t,v_1) + d(u_1,v_2) + \cdots + d(u_t,v_t), $$

with $u_0$ fixed.

The key observation is not to force an artificial reindexing, but to identify which variables each term depends on:

  • Each edge term $d(u_{k-1},u_k)$ depends only on $u_{k-1},u_k$.
  • Each service term $d(u_k,v_j)$ depends only on a single $u_k$.

Thus every occurrence of $u_k$ in $F$ is contained in terms of the form:

  • $d(u_{k-1},u_k)$,
  • $d(u_k,u_{k+1})$,
  • and exactly one service term $d(u_k,v_{k+1})$ for $k<t$, while $u_t$ appears in $d(u_t,v_1)$ and $d(u_t,v_t)$.

So the objective is not globally separable, but it is locally 3-term coupled at each interior index.

Crucially, changing $u_k$ affects only terms in which $u_k$ appears, namely:

$$ d(u_{k-1},u_k),\quad d(u_k,u_{k+1}),\quad d(u_k,v_{k+1}). $$

This is a correct locality statement because no other term involves $u_k$.

This fixes the main structural issue: locality is valid, but only in this restricted sense.

2. Key median inequality in median graphs

Let $G$ be a median graph. For any triple of vertices $a,b,c$, let $m=(a,r,b,c)$ be their median. Then:

  1. $m$ lies on shortest paths between every pair.
  2. Distance splits:

$$ d(a,b)=d(a,m)+d(m,b),\quad \text{and cyclically}. $$ 3. The median minimizes the sum:

$$ d(a,x)+d(b,x)+d(c,x) $$

over all $x$, with strict improvement unless $x=m$.

This property is the correct tool, but it must be applied to fixed triples, not moving ones.

3. Correct local optimization step

Fix an index $1 \le k < t$. Define the local cost contribution of $u_k$ as

$$ \Phi_k(x) = d(u_{k-1},x) + d(x,u_{k+1}) + d(x,v_{k+1}). $$

All other terms in $F$ are independent of $u_k$.

Thus optimizing $u_k$ reduces to minimizing $\Phi_k(x)$.

By the median property applied to the triple

$$ (u_{k-1},, u_{k+1},, v_{k+1}), $$

the unique minimizer of $\Phi_k(x)$ is

$$ u_k = (u_{k-1}, r, u_{k+1}, v_{k+1}). $$

This step is now valid because:

  • the triple is fixed when optimizing $u_k$,
  • no other variable is altered during this local comparison,
  • all affected terms are exactly those in $\Phi_k$.

No circularity is present.

4. Boundary condition at $u_t$

At the last index, the objective contains only:

$$ d(u_{t-1},u_t) + d(u_t,v_1) + d(u_t,v_t). $$

Hence $u_t$ is optimized independently and is the median of:

$$ (u_{t-1}, v_1, v_t), $$

but the problem imposes the constraint $u_t = v_t$, so we simply fix:

$$ u_t = v_t. $$

This turns the last step into a boundary constraint rather than a free optimization variable.

5. Global optimality (correct exchange argument)

Let $(u_1,\dots,u_t)$ be any feasible sequence with $u_t=v_t$.

If for some $k<t$, $u_k$ is not the median of $(u_{k-1},u_{k+1},v_{k+1})$, then replacing $u_k$ by

$$ m_k = (u_{k-1}, r, u_{k+1}, v_{k+1}) $$

strictly decreases $\Phi_k$, hence strictly decreases the total objective $F$, since all other terms are unchanged.

Therefore any global minimizer must satisfy:

$$ u_k = (u_{k-1}, r, u_{k+1}, v_{k+1}) \quad (1 \le k < t). $$

This resolves the earlier invalid exchange argument: the change affects only $\Phi_k$, and this is now correctly isolated.

6. Existence and elimination of circularity

The previous circular definition is avoided by reversing the logic:

  • We do not construct $u_k$ from both neighbors.
  • Instead, we characterize optimal solutions as those satisfying a system of local median constraints.

Existence follows from a standard finite improvement principle:

  • The set of sequences is finite (assuming finite graph or restricting to finite metric closure),
  • each violating index admits a strict improvement,
  • repeated improvements terminate,
  • any terminal configuration satisfies all median conditions simultaneously.

Thus an optimal solution exists and satisfies all local median equations.

No simultaneous definition is required.

7. Conclusion

In a median graph, an optimal sequence $(u_1,\dots,u_t)$ with $u_t=v_t$ is characterized by the local conditions:

$$ u_k = (u_{k-1}, r, u_{k+1}, v_{k+1}) \quad \text{for } 1 \le k < t, $$

together with the boundary constraint:

$$ u_t = v_t. $$

This follows because:

  • each $u_k$ affects only a well-defined local cost $\Phi_k$,
  • median graphs ensure that each $\Phi_k$ is minimized at the median of its three defining vertices,
  • improving any violated index strictly decreases the total cost,
  • hence global optimality is equivalent to simultaneous local optimality.

∎