Martin Nägele:驳斥Goemans关于最小度有界生成树的猜想

在度有界生成树问题中，给出了一个无向图，它具有边代价和每个顶点的度界。任务是找到一个生成树T，它在每个顶点的度不超过度界，并且T是所有生成树中代价最小的。甚至检查一个可行的生成树是否存在也是众所周知的NP-hard。因此，人们对理解轻微违反度约束是否有可能有效地获得成本不大于不违反度约束的最优生成树的生成树的兴趣激增。Goemans在2006年提出了一种基于矩阵向量交集的近似最优算法，该算法最多违背2个单位。2007年，Singh和Lau缩小了这一差距，他们证明迭代松弛允许在违逆程度不超过1的情况下获得相同的结果。除了迭代松弛之外，还没有其他技术可以得到同样的结果。有趣的是，Goemans提出了一个猜想，如果这个猜想是正确的，那就意味着他的矩阵相交方法最多也会违背一个单位。在这项工作中，我们通过驳斥一个更弱的版本来驳斥戈曼斯的猜想。

Simon Bruggmann:关于单来源不可分割的成本流问题

在单源不可分割流问题中，我们给出了一个有向图，该有向图的圆弧被指定了一个容量和一个代价。有许多具有相关需求和终端的商品，任务是将所有商品同时从一个共同的源顶点路由到给定的终端，以便每个商品的需求沿着单一路径路由。

迪尼茨，加格和戈曼斯(1999)表明，任何流动f即允许分割的商品可以转化为不可分割的流动f_unsp它的性质是，对于每一个弧一个，f_unsp（一个)超过f（一个)比最大需求少一个不可分割的流动f_unsp．Goemans推测他们的结果延伸到每一个可分裂的流f，存在不可分割的流f_unsp哪个拥有上面的属性，哪个最昂贵f．

我们证明了这个猜想对两种特殊情况成立。对于第一种情况，我们要求给定的图是2层的，我们提出了一种基于迭代松弛的算法，并在这种情况下证明了猜想。我们要证明猜想的第二种情况是，所有需求都相等，只有一个需求可能更大。特别地，这对只有两种商品的情况下的猜想产生了肯定的答案。