论文标题
关于最低成本转移问题的最快笔记
A Note on the Quickest Minimum Cost Transshipment Problem
论文作者
论文摘要
Klinz和Woeginger（1995）证明，最低成本最快的流量问题是NP-HARD。另一方面，可以通过直接减少到最快的流量问题而无需成本来有效地解决最快的最低成本流问题。更普遍地，我们展示了如何将最快的最低成本转移问题减少到有效解决的最快转运问题中，从而将另一个镶嵌瓷砖添加到了随着时间的流逝的丰富复杂性景观中。
Klinz and Woeginger (1995) prove that the minimum cost quickest flow problem is NP-hard. On the other hand, the quickest minimum cost flow problem can be solved efficiently via a straightforward reduction to the quickest flow problem without costs. More generally, we show how the quickest minimum cost transshipment problem can be reduced to the efficiently solvable quickest transshipment problem, thus adding another mosaic tile to the rich complexity landscape of flows over time.
