## Report in Wirtschaftsmathematik (WIMA Report)

### Refine

#### Keywords

- combinatorial optimization (2)
- Approximation (1)
- Approximation (1)
- Box Algorithms (1)
- Box-Algorithm (1)
- Decision support (1)
- Discrete Bicriteria Optimization (1)
- Dynamic Network Flows (1)
- FPTAS (1)
- Knapsack problem (1)

- 89 rev.
- Algorithms for Time-Dependent Bicriteria Shortest Path Problems (revised version) (2004)
- In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature.

- 90
- A Survey of Approximation Methods in Multiobjective Programming (2003)
- Approaches to approximate the efficient and Pareto sets of multiobjective programs are reviewed. Special attention is given to approximating structures, methods generating Pareto points, and approximation quality. The survey covers 48 articles published since 1975.

- 94
- Multiple Objective Minimum Cost Flow Problems: A Review (2005)
- In this paper, theory and algorithms for solving the multiple objective minimum cost flow problem are reviewed. For both the continuous and integer case exact and approximation algorithms are presented. In addition, a section on compromise solutions summarizes corresponding results. The reference list consists of all papers known to the autheors which deal with the multiple objective minimum cost flow problem.

- 95
- Finding Representative Systems for Discrete Bicriteria Optimization Problems by Box Algorithms (2005)
- Given a discrete bicriteria optimization problem (DBOP), we propose two versions of an approximation procedure, the box algorithm, which results in a representation of the complete set of nondominated solutions by a finite representative system Rep satisfying the following quality features.

- 96
- An Improved Epsilon-Constraint Method for Multiobjective Programming (2005)
- In this paper we revisit one of the most important scalarization techniques used in multiobjective programming, the \(\varepsilon\)-constraint method.

- 100
- Acquisition Prioritization: A Multicriteria Approach Based on a Case Study (2006)
- Selection of new projects is one of the major decision making activities in any company. Given a set of potential projects to invest, a subset which matches the company's strategy and internal resources best has to be selected. In this paper, we propose a multicriteria model for portfolio selection of projects, where we take into consideration that each of the potential projects has several - usually conflicting - values.

- 102
- Connectedness of Efficient Solutions in Multiple Objective Combinatorial Optimization (2006)
- Connectedness of efficient solutions is a powerful property in multiple objective combinatorial optimization since it allows the construction of the complete efficient set using neighborhood search techniques. In this paper we show that, however, most of the classical multiple objective combinatorial optimization problems do not possess the connectedness property in general, including, among others, knapsack problems (and even several special cases of knapsack problems) and linear assignment problems. We also extend already known non-connectedness results for several optimization problems on graphs like shortest path, spanning tree and minimum cost flow problems. Different concepts of connectedness are discussed in a formal setting, and numerical tests are performed for different variants of the knapsack problem to analyze the likelihood with which non-connected adjacency graphs occur in randomly generated problem instances.

- 122
- Earliest Arrival Flows in Series-Parallel Graphs (2009)
- We present an exact algorithm for computing an earliest arrival flow in a discrete time setting on series-parallel graphs. In contrast to previous results for the earliest arrival flow problem this algorithm runs in polynomial time.

- 130
- Min-Max Quickest Path Problems (2010)
- 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.

- 131
- Generalized Multiple Objective Bottleneck Problems (2010)
- 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.