Refine
Year of publication
- 2010 (1) (remove)
Document Type
- Preprint (1) (remove)
Language
- English (1)
Has Fulltext
- yes (1)
Keywords
- bottleneck (1)
- combinatorial optimization (1)
- k-max (1)
- multiple objective (1)
Faculty / Organisational entity
We consider multiple objective combinatiorial optimization problems in which the first objective is of arbitrary type and the remaining objectives are either bottleneck or k-max objective functions. While the objective value of a bottleneck objective is determined by the largest cost value of any element in a feasible solution, the kth-largest element defines the objective value of the k-max objective. An efficient solution approach for the generation of the complete nondominated set is developed which is independent of the specific combinatiorial problem at hand. This implies a polynomial time algorithm for several important problem classes like shortest paths, spanning tree, and assignment problems with bottleneck objectives which are known to be NP-hard in the general multiple objective case.