The complexity of geometric scaling

Geometric scaling, introduced by Schulz and Weismantel in 2002, solves the integer optimization problem max ⁡ { c ⋅ x : x ∈ P ∩ Z n } by means of primal augmentations, where P ⊂ R n is a polytope. We restrict ourselves to the important case when P is a 0/1-polytope. Schulz and Weismantel showed that no more than O ( n log 2 ⁡ n ‖ c ‖ ∞ ) calls to an augmentation oracle are required. This upper bound can be improved to O ( n log 2 ⁡ ‖ c ‖ ∞ ) …