06073716

a

06073716 Kir\'aly, Zolt\'an Kov\'acs, P\'eter An experimental study of minimum cost flow algorithms. Egri-Nagy, Attila (ed.) et al., Proceedings of the 8th international conference on applied informatics (ICAI 2010), Eger, Hungary, January 27--30, 2010. 2 Volumes. Eger: BVB Nyomda \'es Kiad\'o Kft. (ISBN 978-963-9894-72-3/pbk). 227-235 (2012). 2012 Eger: BVB Nyomda \'es Kiad\'o Kft. EN Summary: This paper presents an experimental study of efficient algorithms for the minimum cost flow problem. It is more comprehensive than earlier surveys both in terms of the range of considered implementations and the size of the test instances. In the cost scaling algorithm, Goldberg's partial augment-relabel method was also applied, which is a novel result. The studied algorithms were implemented as part of the LEMON C++ optimization library (\url{http://www.lemon.cs.elte.hu}). They were compared to widely known efficient solvers, namely, the corresponding method of the LEDA library and three public codes: CS2, RelaxIV, and MCF. Our implementations turned out to be comparable and often superior to them.