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.
Verfasser*innenangaben: | Jochen Gorski, Kathrin Klamroth, Stefan Ruzika |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-16686 |
Schriftenreihe (Bandnummer): | Report in Wirtschaftsmathematik (WIMA Report) (131) |
Dokumentart: | Preprint |
Sprache der Veröffentlichung: | Englisch |
Jahr der Fertigstellung: | 2010 |
Jahr der Erstveröffentlichung: | 2010 |
Veröffentlichende Institution: | Technische Universität Kaiserslautern |
Datum der Publikation (Server): | 09.12.2010 |
Freies Schlagwort / Tag: | bottleneck; combinatorial optimization; k-max; multiple objective |
Fachbereiche / Organisatorische Einheiten: | Kaiserslautern - Fachbereich Mathematik |
DDC-Sachgruppen: | 5 Naturwissenschaften und Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |