Groupe d’études et de recherche en analyse des décisions

Is MmC Polynomial for LP?

Jacques Desrosiers Professeur titulaire, Département de sciences de la décision, HEC Montréal, Canada

The minimum mean cycle algorithm (MmC) is known to be strongly polynomial for the capacitated network flow problem with \(O(m^2n)\) iterations, where \(m\) is the number of arc variables and \(n\) is the number of node constraints. In this talk, we examine some properties of MwC, the weighted version of MmC adapted to Linear Programming. In particular, we show that IPS, the Improved Primal Simplex algorithm, is an approximation of MwC.