KLUEDO RSS FeedNeueste Dokumente / Latest documents
https://kluedo.ub.uni-kl.de/index/index/
Thu, 03 Feb 2011 16:45:38 +0100Thu, 03 Feb 2011 16:45:38 +0100Reliable and Restricted Quickest Path Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288
In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.Stefan Ruzika; Markus Thiemannreporthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2288Wed, 02 Mar 2011 16:45:38 +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 +0100