css - 计算返回最大网络流量的最优捐赠分配的难度

Question

我希望有人可以花一些时间考虑以下问题，欢迎一起讨论。问题如下：

对于给定的加权有向网络，作为一个中央权威，他的任务是找到最优的捐赠分配，用m表示，( m是一个向量，m =(m_1, m_2, ...m_n) 其中 m_i 表示有多少商品权限分配给v_i，n是网络中的节点数），它可以返回网络中的最大流量（<em>所有流量的总和）。详细规则如下：

1. 捐赠给节点的物品是可分割的，但物品的总量是有限的。比方说，用M表示的捐赠总额。（想象一下，你正在为网络中的节点分配一个有限的加权蛋糕）。中央当局必须将所有商品捐赠给节点。

2. 在将货物分配给节点后，每个节点 v_i 将 通过 **出向边按比例**将她拥有的东西分配给她的邻居。

• 具体来说，“每个节点拥有的东西”由两部分组成，一是来自中央机构的分配（捐赠）数量，另一部分是它通过传入边缘从其邻居分发中获得的商品数量。例如，考虑在此处输入图像描述中所示的网络，左边的网络是原网络，虚线方块上的东西是按权限分配的调度表，即分别给v_1、v_2各分配1个。那么在这种情况下，v_2 拥有的是 2，等于“授权分配的 1”加上 v_1 分配的另一个 1，因为一旦 v_1 收到授权的 1 捐赠，那么它会将 1 传递（分配）给邻居 v_2。此外，v_1 拥有的只有 1 来自权威捐赠。相反，v_3 的 2 仅来自 v_2 的分布。 因此，简而言之，每个节点所拥有的等于它收到的捐赠，以及它从邻居的分布中获得的捐赠。
• “比例性”每个节点根据每条出边的相对权重按比例分配自己拥有的东西，例如图中，同样在这里输入图像描述，v_2拥有的也是2，因为v_2有两条出边和每个出边的相对权重分别为 3/(2+3)、2/(2+3)，因此，v_2 将 6/5 分配给 v_4，4/5 分配给 v_3。

3. 第三条规则称为“有限责任”，即如果节点拥有的不小于每条出边的权重（容量）之和，则该节点要分配的就是权重（容量）之和的所有出边。否则，节点必须按比例分配它所拥有的一切。例如，如在此处输入图像描述所示，v_1 有 3 个（来自捐赠），但其总出边容量为 2，因此 v_1 只能分配 2 个 v_2。另外，v_2 有 5 小于 6 (4+2)，因此 v_2 按比例分配到 v_3、v_4 之间，因此 v_4 有 5*2/3=10/3 大于 3，因此 v_4 只给出1 到 v_5、v_6 和 v_7。

还有一个具体的例子，如在此处输入图像描述所示，假设有一个权限为 8 的捐赠（可整除），该权限需要决定如何在网络内的节点之间分配 8 个捐赠，以使总数最大化在网络中流动。

假设权限决定分别给6和2提供节点v_1和节点v_3，即m_1=6，m_3=2，其他为0，那么捐赠后的总流量为（1+2+2+8 /5+12/5+3)如图所示，详细计算如下：

首先，由于对 v_1 的捐赠是 6，不小于 v_1 的总输出权重 (1+2+3)，因此 v_1 和 v_2、v_4、v_4 之间的每条边都会被充分利用。此外，v_2 将 2 发送给 v_3，因此 v_3 拥有的是 (2+2)，这等于来自 v_2 的分配和来自当局的捐赠之和。然后 v_3 将其所有 (4) 按比例分配给 v_1 和 v_4，从而导致边缘上的 8/5、12/5 分别从 v_3 流到 v_1 和 v_4。

我认为最后一个例子展示了如何计算给定捐赠分配的流量，但我没有展示如何进行捐赠分配以便我们可以获得网络中的最大总流量，这实际上是我想问的问题。

据我所知，对于任何给定的捐赠分配，可以在多项式时间内计算确切的流量，因此无需担心给定捐赠分配的计算流量。然而，对于任何有 n 个节点的网络，返回最大总流量的最优捐赠分配是否容易计算？这是一个NP难题吗？

标签： cssnetworkingoptimizationflownp