Author: ZmnSCPxj 2021-08-24 01:06:25
Published on: 2021-08-24T01:06:25+00:00
In a conversation between Stefan and Zmn, Stefan discussed his observations on Zmn's definition of `computeCost`. Stefan believes that the definition is really important in solving min-cost flow problems, and it generally has to be separable and convex. However, Zmn pointed out that it depends on what min flow cost algorithms actually assume of the "numbers" being used. He explained that Dijkstra-A*Greedy family of algorithms do not handle negative costs and if you restrict the type to naturals, Dijkstra and its family of algorithms work. Zmn also mentioned that as he is not a 'mathist', he cannot understand the definitions of "separable" and "convex". He asked for the operations involved and their laws for the data type to be "separable" and "convex". He also asked if he needs some specific operations like `*` and `/` or if `type Cost = UnifiedCost` would suffice. Finally, he linked a page that had pseudocode for min-cost flow algorithms.
Updated on: 2023-06-03T05:34:51.630050+00:00