Giorgi Gvatua:
Exploration of Minimum Cost Flow Algorithms
Kurzbeschreibung
The Minimum Cost Flow problem is one of the cornerstones in optimization and graph theory, having a wide variety of applications in telecommunications, logistics, supply chain management, and bipartite matching. This work concentrates on unit-capacity networks, revisiting basic MCF algorithms that demonstrate both their special challenges and their opportunities for optimization. The two algorithmic frameworks considered in some detail include the Pseudoflow Framework, which deploys cost-scaling methods to achieve computational efficiency, and the Cycle Canceling Framework, which generates a sequence of feasible solutions where each successive solution is improved through the elimination of negative-cost cycles. Comparative analysis highlights the trade-offs in computational complexity and practical applicability, stating the strengths of the Pseudoflow Framework for dense network applications, while the Cycle Canceling Framework has the best advantage in sparse or incremental optimizations. The work now synthesizes especially those advances on the work of Goldberg et al. and also advises the route forward, including hybrid methodologies and integrations with emergent computational paradigms. This thesis contributes to both the theoretical understanding and practical implementation of MCF algorithms and gives insight into how scalable and efficient solutions for real-world network optimization problems can be achieved.