algorithm - 最大化有向图中的最小边+节点值

Question

我有一个有向图。每条边都有一个固定的固有“权重”w_ij。每个节点都有一个可以配置的值 v_i，除了“根节点”(没有传入边)和“叶节点”(没有传出边)，它们的值是固定的。

每条边的“由节点调整”边值由下式给出:s_ij = w_ij + v_j - v_i 也就是说，我们通过相邻节点值的差异来调整边的值。当然，改变节点的值会影响s_ij的值。

我对 min{s_ij} 的值很感兴趣，想找到节点的最佳分配值，使这个“瓶颈”值最大化。

关于如何做到这一点有什么想法吗？

注意:循环和从根到叶的“固定路径”提供了最小值的上限(例如，在一个循环中，节点差异的总和始终为 0，因此您最好可以得到的是边缘固有权重的平均值)。但由于周期和“固定路径”可能会重叠，因此尚不清楚是否可以达到最小上限。解决方案很可能首先涉及找到这样的路径/循环。

Answer 1

如果我理解正确的话，这个问题可以表述为这个线性程序。调整输入，使作为源或汇的每个顶点 i 的 v_i = 0。

maximize z

subject to
for every ij,
    z + v_i - v_j <= w_ij  (i.e., z <= w_ij + v_j - v_i = s_ij)

variables
z unbounded
for every vertex i not a source or sink,
    v_i unbounded

这是对偶程序。

minimize sum_ij of w_ij y_ij

subject to
sum_ij y_ij >= 1
for every vertex i not a source or sink,
    sum_j y_ij - sum_j y_ji = 0

variables
for every ij,
    y_ij >= 0

如果我们不从保护约束中排除源和汇，这将是最小平均成本周期的线性规划。就目前情况而言，我们仍然可以使用流分解技术来证明最优存在，即源-汇路径或循环，我相信对用于寻找最小平均成本循环的简单算法稍作修改是适用于此处。

获得最佳值 z* 后，您可以通过使用权重 w_ij - z* 运行 Bellman-Ford 来找到势 v_i .对于没有提供更多细节，我深表歉意，但我有一种挥之不去的感觉，好像我在做你的功课。