Lexicographic bottleneck combinatorial problems

We study combinatorial problems (CP) with lex-bottleneck objective function, where in addition to minimizing the largest element of a feasible solution, we are also interested in minimizing the second largest element, the third largest element, and so on. We consider CP, and in particular path, assignment and general matching problems, whose corresponding (zero–one) sum optimization problems can be solved as linear programs. Let t = min(k, l), where k is the number of distinct weights of elements and l the maximum number of elements in any feasible solution. We propose an approach which solves the lex-bottleneck optimization problem by solving bottleneck and zero–one sum optimizations for at most t iterations and reducing the problem size in each iteration. We also propose another approach which is similar to the above approach but solves only zero–one sum optimizations for at most k iterations. For a graph with n nodes and m arcs, the first approach solves the lex-bottleneck path problem in O(nm) time, and the second approach solves the lex-bottleneck assignment problem in O(m²) time. For lex-bottleneck general matching problem, a time bound of O(min(m, n log n)n(m + n logn)) is given.