Thanks a lot. Is there another algorithm for solving the MCF problem? is it better than NS?
Regards, Heba ________________________________________ From: Kovács Péter <[email protected]> Sent: Monday, September 1, 2014 12:11 PM To: Alpár Jüttner; T.A. Heba Essam Cc: [email protected] Subject: Re: Run time complexity of network simplex algorithm 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 > <[email protected] <mailto:[email protected]>> 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 > > _______________________________________________ Lemon-user mailing list [email protected] http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
