KLUEDO RSS FeedKLUEDO Dokumente/documents
https://kluedo.ub.uni-kl.de/index/index/
Wed, 19 Jun 2013 08:27:31 +0200Wed, 19 Jun 2013 08:27:31 +0200On the Generality of the Greedy Algorithm for Solving Matroid Base Problems
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535
It is well known that the greedy algorithm solves matroid base problems for all linear cost functions and is, in fact, correct if and only if the underlying combinatorial structure of the problem is a matroid. Moreover, the algorithm can be applied to problems with sum, bottleneck, algebraic sum or \(k\)-sum objective functions.Lara Turner; Matthias Ehrgott; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/3535Wed, 19 Jun 2013 08:27:31 +0200Universal Shortest Paths
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230
We introduce the universal shortest path problem (Univ-SPP) which generalizes both - classical and new - shortest path problems. Starting with the definition of the even more general universal combinatorial optimization problem (Univ-COP), we show that a variety of objective functions for general combinatorial problems can be modeled if all feasible solutions have the same cardinality. Since this assumption is, in general, not satisfied when considering shortest paths, we give two alternative definitions for Univ-SPP, one based on a sequence of cardinality contrained subproblems, the other using an auxiliary construction to establish uniform length for all paths between source and sink. Both alternatives are shown to be (strongly) NP-hard and they can be formulated as quadratic integer or mixed integer linear programs. On graphs with specific assumptions on edge costs and path lengths, the second version of Univ-SPP can be solved as classical sum shortest path problem.Lara Turner; Horst W. Hamacherpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/2230Mon, 16 Aug 2010 11:00:30 +0200A Level Set Method for Multiobjective Combinatorial Optimization: Application to the Quadratic Assignment Problem
https://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1352
Multiobjective combinatorial optimization problems have received increasing attention in recent years. Nevertheless, many algorithms are still restricted to the bicriteria case. In this paper we propose a new algorithm for computing all Pareto optimal solutions. Our algorithm is based on the notion of level sets and level curves and contains as a subproblem the determination of K best solutions for a single objective combinatorial optimization problem. We apply the method to the Multiobjective Quadratic Assignment Problem (MOQAP). We present two algorithms for ranking QAP solutions and nally give computational results comparing the methods.Matthias Ehrgott; Thomas Stephan; Dagmar Tenfelde-Podehlpreprinthttps://kluedo.ub.uni-kl.de/frontdoor/index/index/docId/1352Tue, 15 Oct 2002 22:29:00 +0200