English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Motivated by Bland's linear-programming generalization of the renownedEdmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm,we discuss three closely-related natural augmentation rules for linear andinteger-linear optimization. In several nice situations, we show thatpolynomially-many augmentation steps suffice to reach an optimum. Inparticular, when using "discrete steepest-descent augmentations" (i.e.,directions with the best ratio of cost improvement per unit 1-norm length), weshow that the number of augmentation steps is bounded by the number of elementsin the Graver basis of the problem matrix, giving the first ever stronglypolynomial-time algorithm for $N$-fold integer-linear optimization. Our resultsalso improve on what is known for such algorithms in the context of linearoptimization (e.g., generalizing the bounds of Kitahara and Mizuno for thenumber of steps in the simplex method) and are closely related to research onthe diameters of polytopes and the search for a strongly polynomial-timesimplex or augmentation algorithm.

On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds-Karp to Bland and Beyond