[Lemon-user] Runtime of min cost flow algorithms

[Kovács Péter]

Dear Ben,

Yes, the documentation should contain the theoretical running times of 
all algorithms. For min cost flow algorithms, they are the following.

   * CycleCanceling:
       - SIMPLE_CYCLE_CANCELING: no polynomial bound is known
       - MIN_MEAN_CYCLE_CANCELING: strongly poly. O(n^2 m^3 log(n))
       - CANCEL_AND_TIGHTEN: strongly poly. O(n^2 m^2 log(n))
     The CANCEL_AND_TIGHTEN method is the default. It is orders of 
magnitude faster than the other two in practice, too.

   * CapacityScaling: O(m log(U) (m + n log n)),
     where U denotes the max supply value

   * CostScaling: O(n^2 m log(nC)),
     where C denotes the max cost value

   * NetworkSimplex: no polynomial bound is known


Note that these worst case times are usually far from the practical 
performance. Therefore, we made a lot of benchmark tests on various test 
inputs. Our results can be summarized as follows.

   * In most cases, NetworkSimplex and CostScaling are the fastest. For 
not too large graphs, NetworkSimplex outperforms all the other methods. 
However, CostScaling is faster for large and relatively sparse networks.

   * CapacityScaling and CycleCanceling algorithms are usually 
significantly slower than the other two methods, except for some special 
cases. E.g. if the problem is so simple that the optimal solution 
consists of only a few paths, then CapacityScaling can be much faster 
than the others.

   * Our implementations are always competitive and often superior to 
other widely used efficient solvers (both open source and commercial ones).

For more information, you may find a detailed presentation of these 
methods and our benchmark results here:
http://people.inf.elte.hu/kpeter/download/mcf_presentation_icai_2010.pdf

Best regards,
Peter


> Hello,
>
> the min cost flow algorithms seem to be missing their worst case
> runtimes in the documentation. I'm having a pretty hard time guessing
> them because most of the literatur uses different problem formulations
> (often without lower arc capacities) and I'm unsure how far this affects
> the runtime. I need the runtimes of CapacityScaling and the Circulation
> algorithms.
>
> Thank you,
> Ben Strasser
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user