[Lemon-user] Run time complexity of network simplex algorithm

[Kovács Péter]

Hi,

Actually, a theoretical running time bound O(nm^2CU) holds for the 
algorithm, where U and C denote the largest arc capacity and the largest 
arc cost.

However, as Alpár wrote, this bound is not polynimial in terms of the 
size of the network (as it also depends on the magnitudes of capacity 
and cost values), and it really does not reflect to the practical 
performance of the algorithm.

All in all, we can hardly say more than that the algorithm is proved to 
be finite and is really efficient in practice.

Regards,
Peter


> Hi,
>
> Unfortunately - in line with the normal simplex algorithm for solving LP
> instances - there is big gap between the practical and theoretic worst
> case running time of the network simplex.
> Namely, the worst case running time of NS is exponential, however on
> practical examples it almost always outperforms the best known
> polynomial algorithms for the same problem.
>
> Regards,
> Alpár
>
>
>
> On Mon, Sep 1, 2014 at 12:57 PM, T.A. Heba Essam
> <Heba.Essam at cis.asu.edu.eg <mailto:Heba.Essam at cis.asu.edu.eg>> wrote:
>
>     Dears,
>
>     Can you please provide me with the run time complexity of the
>     network simplex algorithm used in LEMON for solving the MCF problem
>     in terms of /O(??). /
>
>     //
>
>     I'm using it within an algorithm of mine and I need to calculate the
>     overall time complexity of my algorithm.
>
>     Thanks a lot,
>
>     Heba
>
>