TAOCP 7.1.4 Exercise 21

Exercise 21. [05] [05] Can Algorithm B minimize w1x1 + · · · + wnxn, instead of maximizing it?

Verified: yes
Solve time: 51s

Yes. Minimizing

$$ w_1x_1+\cdots+w_nx_n $$

is equivalent to maximizing its negative,

$$ -(w_1x_1+\cdots+w_nx_n)=(-w_1)x_1+\cdots+(-w_n)x_n. $$

Therefore Algorithm B can be applied without any structural change: Replace each weight $w_k$ by $-w_k$, execute the maximization algorithm exactly as stated, and return the resulting assignment. If the maximum value obtained for the negated weights is $M$, the minimum value of the original objective is $-M$.

This transformation is correct because, for any two assignments $x$ and $y$,

$$ w(x)\le w(y) \quad\Longleftrightarrow\quad -w(x)\ge -w(y), $$

so the assignment that maximizes the negated objective is precisely the assignment that minimizes the original one. Thus Algorithm B minimizes the weighted sum simply by c