A STRONGLY POLYNOMAL- TIME ALGORITHM FOR A CLASS OF INTEGER PROGRAMMING PROBLEMS

Abstract

In this paper a strongly polynomial-time algorithm is proposed for solving exactly a class of integer programming problems which is basically to minimize the pointwise maximum of n affine functions under m semiassignment constraints and upper bound constraints. The algorithm is based on a numbering technique for improving feasible solutions.