Kaiserslautern - Fachbereich Mathematik
Refine
Year of publication
- 2010 (2) (remove)
Language
- English (2)
Has Fulltext
- yes (2)
Keywords
- bottleneck (1)
- combinatorial optimization (1)
- fptas (1)
- k-max (1)
- multiple objective (1)
- multiple objective optimization (1)
- polynomial algorithms (1)
- quickest path (1)
- robust network flows (1)
Faculty / Organisational entity
In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example in evacuation or transportation planning, the problem parameters might not be known exactly a-priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, min-max versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed.
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.