404 "Minimum Cost Flow Problem". |
404 "Minimum Cost Flow Problem". |
405 |
405 |
406 LEMON contains several algorithms for this problem. |
406 LEMON contains several algorithms for this problem. |
407 - \ref NetworkSimplex Primal Network Simplex algorithm with various |
407 - \ref NetworkSimplex Primal Network Simplex algorithm with various |
408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. |
408 pivot strategies \ref dantzig63linearprog, \ref kellyoneill91netsimplex. |
409 - \ref CostScaling Push-Relabel and Augment-Relabel algorithms based on |
409 - \ref CostScaling Cost Scaling algorithm based on push/augment and |
410 cost scaling \ref goldberg90approximation, \ref goldberg97efficient, |
410 relabel operations \ref goldberg90approximation, \ref goldberg97efficient, |
411 \ref bunnagel98efficient. |
411 \ref bunnagel98efficient. |
412 - \ref CapacityScaling Successive Shortest %Path algorithm with optional |
412 - \ref CapacityScaling Capacity Scaling algorithm based on the successive |
413 capacity scaling \ref edmondskarp72theoretical. |
413 shortest path method \ref edmondskarp72theoretical. |
414 - \ref CancelAndTighten The Cancel and Tighten algorithm |
414 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are |
415 \ref goldberg89cyclecanceling. |
415 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling. |
416 - \ref CycleCanceling Cycle-Canceling algorithms |
|
417 \ref klein67primal, \ref goldberg89cyclecanceling. |
|
418 |
416 |
419 In general NetworkSimplex is the most efficient implementation, |
417 In general NetworkSimplex is the most efficient implementation, |
420 but in special cases other algorithms could be faster. |
418 but in special cases other algorithms could be faster. |
421 For example, if the total supply and/or capacities are rather small, |
419 For example, if the total supply and/or capacities are rather small, |
422 CapacityScaling is usually the fastest algorithm (without effective scaling). |
420 CapacityScaling is usually the fastest algorithm (without effective scaling). |