A competitive (dual) simplex method for the assignment problem

Where there is abundance of mystery and confusion in every direction, the truth seldom remains hidden for long. It's a matter of having plenty of angles to go at it from. Only the utterly simple crimes - the simplex crimes, you may say - have the trick of remaining baffling. - Sir John (from Michael Innes,The Open House (A Sir John Appleby Mystery), Penguin Books, 1974).A dual simplex method for the assignment problem leaves open to choice the activity (i,j) of rowi and columnj that is to be dropped in pivoting so long asx_ij < 0. A choice (i,j) over columnsj having at least 3 basic activities that minimizesx_ij is shown to converge in at most (₂^n-1) pivots, and at most O(n³) time, and it is argued that on average the number of pivots is at mostn logn.Dedicated with affection to George B. Dantzig on the occasion of his seventieth birthday.