Generalized Multiple Objective Bottleneck Problems

  • 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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
Author:Jochen Gorski, Kathrin Klamroth, Stefan Ruzika
URN:urn:nbn:de:hbz:386-kluedo-16686
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (131)
Document Type:Preprint
Language of publication:English
Year of Completion:2010
Year of first Publication:2010
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2010/12/09
Tag:bottleneck; combinatorial optimization; k-max; multiple objective
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
Licence (German):Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011