Spanner Problems and Multiple Objectives

点击翻译按钮获取中文摘要

Given a graph $G$, probably together with edge lengths and weights. An $\alpha$-spanner is a subgraph of $G$ in which the shortest paths are at most $\alpha$ times longer than in $G$. Typically, one considers the problem of finding a small or cost-minimal spanner for a given $\alpha$. The spanner problem has diverse applications, there are many known research results, in particular in the realm of approximation algorithms, and spanner algorithms regularly appear as an intergal part of other algorithmic results. However, results regaring spanners are quite rare in three other research fields: (a) exact algorithms, (b) algorithm engineering (in particular practical implementations), and (c) multi-criteria variants of the problem (which seem rather typical in practice). In this project, we combine all these three fields in different ways: 1) We consider exact ILP-based methods to solve the classical minimum $\alpha$-spanner problem, both from the theoretical and polyhedral points of view, and regarding practical implementations. Thereby, we will have to solve a pricing problem within a column generation scheme which lends itself to the use of multi-criteria shortest path algorithms. 2) We consider different multi-criteria variants of the spanner problem (e.g., two different cost functions, minimize cost and $\alpha$, etc.). Instead of asking for a single optimal value, we now ask for a full Pareto front (or its extreme points). For such problems we will develop and implement both exact and approximative methods.