无向图中乘积而不是总和的最小权重

Question

我能找到的所有算法都使用最大 flow/minimum 切割 属性 来计算将源与汇分开的最小加权切割。然而，所有这些算法都使用权重之和作为最小值的定义，而在我的用例中，权重不是绝对数字，而是机会，因此必须在乘法而不是加法下最小化以提供适当的最小切割.

我无法证明已知最大 flow/min 切割算法背后的想法和属性仍然适用于乘法而不是加法。这些算法是否可以针对最小的产品重量削减进行调整？如果不是，我可以使用什么算法来计算这样的切割？

Answer 1

Can these algorithms be adjusted for a minimum product weight cut?

是的，使用对数概率作为容量。