An improved general procedure for lexicographic bottleneck problems

In combinatorial optimization, the bottleneck (or minmax) problems are those problems where the objective is to find a feasible solution such that its largest cost coefficient elements have minimum cost. Here we consider a generalization of these problems, where under a lexicographic rule we want to minimize the cost also of the second largest cost coefficient elements, then 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 the 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 optimization problem solution procedure.