一千萬個為什麽

搜索

目前最著名的運輸問題算法是什麽?


考慮眾所周知的運輸問題: 有$ m $供應節點,$ n $需求節點和$ k $可行弧。 每個節點都有一個整數供應或需求,並且弧具有整數成本,線性使用,即如果$ x $單位沿著用$ c $註釋的邊緣發貨,則成本為$ c \ cdot x $。

我有一篇 Kleinschmidt和Schannath 的文章描述$ O(m \ log m(k + n \ log n)) $解決方案。

這是目前最好的算法,還是自1995年以來有所改善?

(我的搜索從2008年開始發布了 Brenner 的一篇文章,但我無法訪問標題談到“不平衡的希區柯克運輸問題”,我不確定這是否是這裏考慮的問題)。

這是正確的算法嗎?

哪些圖書館提供運輸問題的實施?

最佳答案

猜你喜歡