Skip to main content
eScholarship
Open Access Publications from the University of California

UC Davis

UC Davis Previously Published Works bannerUC Davis

On augmentation algorithms for linear and integer-linear programming: From Edmonds-Karp to Bland and beyond

  • Author(s): De Loera, JA
  • Hemmecke, R
  • Lee, J
  • et al.

Published Web Location

http://front.math.ucdavis.edu/1408.3518
No data is associated with this publication.
Abstract

Motivated by Bland's linear programming (LP) generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum flow algorithm, we analyze three closely related natural augmentation rules for LP and integer-linear programming (ILP) augmentation algorithms. For all three rules and in both contexts, LP and ILP, we bound the number of augmentations. Extending Bland's "discrete steepest-descent" augmentation rule (i.e., choosing directions with the best ratio of cost improvement per unit 1-norm length, and then making maximal augmentations in such directions) from LP to ILP, we (i) show that the number of discrete steepest-descent augmentations is bounded by the number of elements in the Graver basis of the problem matrix and (ii) give the first strongly polynomial-time algorithm for N-fold ILP. For LP, two of the rules can suffer from a "zig-zagging" phenomenon, and so in those cases we apply the rules more subtly to achieve good bounds. Our results improve on what is known for such augmentation algorithms for LP (e.g., extending the style of bounds found by Kitahara and Mizuno for the number of steps in the simplex method) and are closely related to research on the diameters of polytopes and the search for a strongly polynomial-time simplex or augmentation algorithm.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item