Spanner Problems and Multiple Objectives

给定一个图G，可能还有边的长度和权。一个$\alpha$-图是$G$的一个子图，其中的最短路径至多是$G$的$\alpha$倍。通常情况下，我们考虑的问题是为给定的$\alpha$找到一个小的或成本最小的节点。该问题有着广泛的应用，有许多已知的研究成果，特别是在近似算法领域，并且该算法经常作为其他算法结果的一部分出现。然而，在其他三个研究领域中，关于spectrum的结果是相当罕见的：（a）精确算法，（B）算法工程（特别是实际实现），（c）问题的多标准变体（在实践中似乎相当典型）。在这个项目中，我们联合收割机以不同的方式结合所有这三个领域：1）我们考虑基于ILP的精确方法来解决经典的最小$\alpha$-最小问题，无论是从理论和多面体的角度来看，并考虑实际的实现。因此，我们将不得不解决一个列生成方案内的定价问题，该方案适用于使用多标准最短路径算法。2)我们考虑不同的多准则变量的问题（例如，两个不同的成本函数，最小化成本和$\alpha$等）。我们现在要求的不是一个单一的最优值，而是一个完整的帕累托前沿（或其极值点）。对于这样的问题，我们将开发和实施精确和近似的方法。

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.