TAOCP 7.2.2.1 Exercise 230

Let each option $O$ in the instance of Fig.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.1: Dancing Links

Exercise 230. [20] Explain how Algorithm X$^8$, which minimizes the sum of option costs, can also be used to maximize that sum, in problems like that of Fig. 74.

Verified: yes
Solve time: 1m31s

Solution

Let each option $O$ in the instance of Fig. 74 carry a cost $c(O)$, and let a solution $S$ of Algorithm X$^8$ be a set of pairwise disjoint options covering all items. The objective in Algorithm X$^8$ is to minimize

$\sum_{O \in S} c(O).$

To convert a maximization problem into this framework, assign to each option a transformed cost

$c'(O) = -c(O).$

For every solution $S$,

$\sum_{O \in S} c'(O) = \sum_{O \in S} (-c(O)) = -\sum_{O \in S} c(O).$

Thus, if $S_1$ and $S_2$ are solutions and

$\sum_{O \in S_1} c(O) \ge \sum_{O \in S_2} c(O),$

then

$\sum_{O \in S_1} c'(O) \le \sum_{O \in S_2} c'(O).$

Hence every solution maximizing $\sum c(O)$ corresponds exactly to a solution minimizing $\sum c'(O)$, and vice versa, with identical feasible sets because Algorithm X$^8$ does not alter the covering constraints, only the accumulated cost.

Since the transformation is applied per option and preserves additivity over solutions, no dependence on the number of selected options arises beyond the sum itself, and no additional items or constraints are required.

Algorithm X$^8$ applied with costs $c'(O) = -c(O)$ therefore produces a solution minimizing $\sum c'(O)$, which is precisely a solution maximizing $\sum c(O)$.

This completes the construction and correctness argument. ∎