## Invited Session Mon.2.H 1029

#### Monday, 13:15 - 14:45 h, Room: H 1029

**Cluster 15: Multi-objective optimization** [...]

### Efficient set representations

**Chair: Luís Paquete**

**Monday, 13:15 - 13:40 h, Room: H 1029, Talk 1**

**Michael Stiglmayr**

The multicriteria linear bottleneck assignment problem

**Abstract:**

We present a solution method for the multicriteria linear bottleneck assignment problem (MLBAP), which is the multicriteria analogon of the well studied linear bottleneck assignment problem. Our algorithm is an extension of the single criteria threshold algorithm. We define a residual graph by specifying a (multicriteria) threshold vector, such that all of its edges have cost dominated by the threshold. Any complete matching in this residual graph is a candidate for an efficient solution with at least the threshold values. The computation of matchings in the residual graph is realized by an efficient update of augmenting paths. Based on our method, which computes the complete efficient set, we also suggest an approximation scheme for the efficient set with an adjustable quality. The uniformity and the dispersity of this representation can be bounded during the run of the algorithm. While we restrict ourselves to bicriteria cases, we show possible extensions to multiple criteria.

**Monday, 13:45 - 14:10 h, Room: H 1029, Talk 2**

**Luís Paquete**

Concise representation of nondominated sets in discrete multicriteria optimization

**Coauthors: Carlos M. Fonseca, Kathrin Klamroth, Michael Stiglmayr**

**Abstract:**

The problem of finding a representative subset of the nondominated point set of a discrete multicriteria optimization problem with respect to uniformity and coverage is introduced. Provided that the decision maker is able to indicate the number of points to visualize, a subset of well-spread points (uniformity) that are close enough to the remaining points (coverage) is of interest.

Finding a representative *p*-point subset with respect to uniformity and coverage can be formulated as a combination of *p*-dispersion and *p*-center facility location problems, respectively, with a special location structure. In this work, polynomial-time dynamic programming algorithms to find representative subsets with respect to each of these measures in the two-dimensional case are presented. Moreover, the multicriteria version of this problem is shown to be solvable also in polynomial time using dynamic programming. The extension of these and related problems to larger dimensions will be discussed.

**Monday, 14:15 - 14:40 h, Room: H 1029, Talk 3**

**Florian Seipp**

A polynomial time approach for the multiple objective minimum spanning tree problem

**Coauthor: Stefan Ruzika**

**Abstract:**

The minimum spanning tree problem is a well-studied problem in combinatorial optimization. Whereas the single objective version can be solved in polynomial time by greedy algorithms, the multiple objective version is known to be intractable and NP-hard. Even worse, the number of both supported and unsupported nondominated points may be exponentially large in the number of edges of the underlying graph.

In this talk, it is shown that it is however possible to bound the number of extremal supported nondominated points polynomially. The result is based on the theory of arrangements of hyperplanes. It immediately implies that the first phase of the two-phases method, i.e., computing the nondominated frontier, can be accomplished by solving a polynomial number of weighted sum problems. A solution approach is presented which demonstrates how this can be achieved algorithmically.