Spanner Problems and Multiple Objectives

给定一个图$G$，可能还有边的长度和权值。$\alpha$-扳手是$G$的子图，其中最短路径最多是$G$的$\alpha$倍长。通常，人们考虑的问题是为给定的$\alpha$找到一个小的或成本最低的扳手。扳手问题具有多种应用，已知的研究成果很多，特别是在近似算法领域，扳手算法经常作为其他算法结果的组成部分出现。然而，关于扳手的结果在其他三个研究领域是相当罕见的：(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.