KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Tue, 08 Feb 2011 12:18:44 +0100Tue, 08 Feb 2011 12:18:44 +0100On a Cardinality Constrained Multicriteria Knapsack Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281
We consider a variant of a knapsack problem with a fixed cardinality constraint. There are three objective functions to be optimized: one real-valued and two integer-valued objectives. We show that this problem can be solved efficiently by a local search. The algorithm utilizes connectedness of a subset of feasible solutions and has optimal run-time.Florian Seipp; Stefan Ruzika; Luis Paquetepreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2281Tue, 08 Feb 2011 12:18:44 +0100Generalized Multiple Objective Bottleneck Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252
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.Jochen Gorski; Kathrin Klamroth; Stefan Ruzikapreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2252Thu, 09 Dec 2010 10:21:17 +0100