我一直在阅读一些关于分割图结构的多重算法的论文。我对这项工作特别感兴趣,它提出了一种算法来解决多切问题的扩展:
关于边缘成本,它说:
...对于任何一对节点,这些节点位于不同组件中的所有分解的实值成本(奖励)
很公平。它进一步说,多割问题的解决方案是一个简单的二进制向量,其长度等于图中的边数,其中“1”表示相应的边将两个属于不同图组件的顶点分开:
对于每条边 vw ∈ E ∪ F ,当且仅当 v 和 w 在 G 的不同分量中时,y(v,w) = 1。
但是优化问题写成:
这似乎没有意义。如果边权重描述了在不同组件中连接节点的边的奖励,这不应该是一个最大化问题吗?在任何一种情况下,如果所有边权重都是正的,那不会导致一个简单的解决方案,其中y
全零向量是什么?上面的表达式后面是论文中的一些约束,但我不知道其中任何一个是如何阻止这种结果的。
此外,当它稍后尝试使用贪婪加性边缘收缩生成初始解决方案时,它说:
阿尔格。1 从分解为单个节点开始。在每次迭代中,连接一对相邻组件,该连接最大程度地降低了目标值。如果没有连接严格减少目标值,则算法终止。
同样,如果边权重是保持节点分离的奖励,那么加入任何两个节点不会减少奖励吗?即使我假设边缘权重是保持节点分离的惩罚,这种方法不会简单地将所有节点集中到一个组件中吗?
我看到这可行的唯一方法是边缘权重是正值和负值的平衡组合,但我很确定我错过了一些东西,因为文献中没有提到这个约束。