Group for Research in Decision Analysis

Is MmC Polynomial for LP?

Jacques Desrosiers Professor, Department of Decision Sciences, 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.