On weighting two criteria with a parameter in combinatorial optimization problems

Two criteria in a combinatorial problem are often combined in a weighted sum objective using a weighting parameter between 0 and 1. For special problem types, e.g., when one of the criteria is a bottleneck value, efficient algorithms are known that solve for a given value of the weighting parameter.We transform the underlying enumeration method into a parametric algorithm solving simultaneously for all values of the weighting parameter. Efficient implementations are presented for combinatorial problems with criteria as balanced optimization, min–sum with min–max, and min–sum with balanced optimization, considering the spanning tree, the linear assignment and the single machine scheduling problem. Further the new algorithmic scheme can easily incorporate a trade-off of the criteria by means of penalty functions, again without consequences for the algorithm and its complexity order.

► A parametric algorithm solves for all combinations of two criteria in a combinatorial problem.
► Efficient implementations treat criteria such as min–sum and min–max or balanced optimization.
► An algorithm of O(m log n) combines the length of a spanning tree and its longest edge.
► With penalty functions one can refine the trade-off between the criteria.