An improved general procedure for lexicographic bottleneck problems
Della Croce, Federico; Paschos, Vangelis; Tsoukiàs, Alexis (1999), An improved general procedure for lexicographic bottleneck problems, Operations Research Letters, 24, 4, p. 187-194. http://dx.doi.org/10.1016/S0167-6377(99)00013-9
TypeArticle accepté pour publication ou publié
Journal nameOperations Research Letters
MetadataShow full item record
Abstract (EN)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.
Subjects / KeywordsCombinatorial optimization; Bottleneck problem; Lexicographic problem
Showing items related by title and author.
Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems Paschos, Vangelis; Della Croce, Federico (2008) Article accepté pour publication ou publié
Lower bounds on the approximation ratios of leading heuristics for the single machine total tardiness problem Grosso, Andrea; Della Croce, Federico; Paschos, Vangelis (2004) Article accepté pour publication ou publié