Genuinely Polynominal Simplex and Non-Simplex Algorithms for the Minimum Cost Flow Problem (Classic Reprint) - Softcover

Inhaltsangabe

Explore how this book reframes the minimum cost flow problem with genuinely polynomial algorithms. It presents new dual simplex approaches and connects them to practical network optimization, offering a clear path from classic methods to modern bounds.

Two concise sections outline the scope and value: first, a historical view of Edmonds–Karp scaling and the search for polynomial-time pivot rules; second, a detailed development of two network dual simplex algorithms with provable performance guarantees. The discussion stays focused on structure, complexity, and implementation insights that matter for researchers and practitioners alike.

• Two genuinely polynomial dual simplex pivot rules for minimum cost flow


• Connections between dual pivots and shortest-path steps, including Dijkstra-based interpretations


• Complexity bounds that compare with Edmonds–Karp scaling and other classical methods


• Guidance on implementing these algorithms for sparse networks and practical use

Ideal for readers of advanced optimization, operations research, and algorithm design who want a rigorous but accessible treatment of network flow methods.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.