| 摘要 |
Multi-way partitioning is dramatically improved based on “weakest-link” optimality. The set of numbers to be partitioned is subjected to pairwise decomposition with a first partition having a candidate subset (P1={S1}), and a lower cost bound cmin is set equal to a maximum cost of this subset. A recursive call is then invoked to resolve the subproblem of the second partition (P2={S2, S3, . . . , Sk}). If each second candidate subset in the second partition has a cost which is less than or equal to the lower cost bound, then the first partition is returned with the second partition as an optimal solution regardless of whether the second partition is an optimal decomposition. Additional efficiency may be achieved by excluding any subset having a cost which is greater than or equal to the best cost so far. Dominated and symmetric solutions can also be excluded. |
