An improved general procedure for lexicographic bottleneck problems

In combinatorial optimization, the bottleneck (or minmax) problems are thos e problems where the objective is to find a feasible solution such that its largest cost coefficient elements have minimum cost. Here we consider a ge neralization of these problems, where under a lexicographic rule we want to minimize the cost also of the second largest cost coefficient elements, th en of the third largest cost coefficients, and so on. We propose a general rule which leads, given the considered problem, to a vectorial version of t he solution procedure for the underlying sum optimization (minsum) problem. This vectorial procedure increases by a factor of k (where k is the number of different cost coefficients) the complexity of the corresponding sum op timization problem solution procedure. (C) 1999 Published by Elsevier Scien ce B.V. All rights reserved.