2294. An adjacency-based algorithm for computing all extreme-supported efficient spanning trees
Invited abstract in session TD-5: Multiobjective Optimization 3: Representations, stream Decision Theory and Multi-criteria Decision Making.
Thursday, 14:30-16:00Room: H7
Authors (first author is the speaker)
| 1. | Oliver Bachtler
|
| Mathematics, RPTU Kaiserslautern-Landau | |
| 2. | Felix Fritz
|
| RPTU Kaiserslautern-Landau | |
| 3. | Stefan Ruzika
|
| Mathematik, Rheinland-Pfälzische Technische Universität Kaiserslautern |
Abstract
Generally, multi-criteria optimisation problems are solved exactly or approximated by solving a series of scalarisations, for example by dichotomic search.
In this talk, we will take a different approach and compute the set of all extreme-supported non-dominated solutions of the bi-criteria minimum spanning tree problem by using a neighbourhood-based approach.
We also look at the generalisation to matroids.
We call two spanning trees adjacent if they have all but one of their edges in common.
Note that, with respect to this neighbourhood definition, neither the set of extreme-supported efficient nor the set of efficient spanning trees is connected.
Additionally, while the set of supported efficient solutions is connected, it can be of exponential size.
Nevertheless, we show how we can traverse the set of supported efficient solutions in such a way that all extreme-supported efficient solutions are found and only a polynomial number of supported efficient solutions are visited.
Finally, we note that the extreme-supported efficient solutions are a {(2,1), (1,2)}-approximation for general multi-criteria optimisation problems and briefly look at how we can transfer results from parametric optimisation to this setting.
Keywords
- Multi-Objective Programming
- Approximation Algorithms
Status: accepted
Back to the list of papers