Published on: 2021-08-30T11:08:52+00:00
In a conversation between Stefan and ZmnSCPxj, the topic of min-cost flow problem and algorithms is discussed. Stefan mentions that the algorithm he found has limitations, as it only works for linear min-cost flow problems and is slow. However, in reality, convex cost functions need to be addressed, which can be done through capacity scaling to make the algorithm faster. The concept of "separable" and "convex" is explained, and Stefan suggests that redefining the definition of adding up may make his definition work. ZmnSCPxj expresses concern about the implementation time and complexity that may arise from adding "subtract" and "multiply" operations, and recommends focusing on the disect algorithm instead.Stefan compliments ZmnSCPxj's lateral thinking and agrees that the computeCost definition is important for solving min-cost flow problems. He believes that the definition generally needs to be separable and convex, but notes that the Dijkstra-A*Greedy family of algorithms do not handle negative costs. ZmnSCPxj questions why cost should be represented as a number and suggests exploring alternative structures that can provide the necessary operations demanded by the mincostflow algorithm.The discussion revolves around alternative pathfinding and the representation of cost as a number. The focus is on the minimum cost flow algorithms and the operations required by the "cost" datatype. The article also delves into the Lightning Network, a second-layer solution for the Bitcoin blockchain aimed at scalability and reducing transaction fees. It discusses the cost of failed payments and proposes a method for estimating payment success probability as a cost function for pathfinding algorithms. Factors such as actual fees and total cltv-delta are considered, and the article introduces the concept of alternative pathfinding using an "aggregate" operation instead of simple addition.Overall, the conversations and article explore various aspects of min-cost flow problems, algorithms, and the Lightning Network. They discuss the limitations of existing algorithms, the importance of the computeCost definition, alternative structures for representing cost, and considerations for improving the efficiency and reliability of the Lightning Network.
Updated on: 2023-07-31T23:45:02.587365+00:00