Author: Stefan Richter 2021-08-24 10:19:39
Published on: 2021-08-24T10:19:39+00:00
The author recommends a textbook to understand the min-cost flow problem and algorithms better. The algorithm discovered has shortcomings, as it will only work for the linear min-cost flow problem and is slow. In reality, convex cost functions need to be dealt with, and the approach used so far uses capacity scaling to be much faster. Separable means that the costs of the edges can be added up to get the total costs, while convex means that the cost function does not lie below the line connecting two points. The Dijkstra-A* greedy family of algorithms does not handle negative costs, and if naturals are used instead of integers, it works. The output of the cost function is a UnifiedCost structure and not a number in the traditional sense.
Updated on: 2023-06-03T05:36:46.120727+00:00