On algorithms for discrete problems

AbstractThe paper presents a theorem, applicable to many algorithms used in integer programming, which states that, under frequently met hypotheses, arbitrarily close (in the topology on real space) to most “well-behaved” integer programs there exist integer programs for which the algorithm requires arbitrarily many iterations to solve.Primary among the hypotheses of the theorem is the supposition that, in the determination of the next operation to be undertaken (perhaps addition of a cut row, or a pivot step, etc), the space of all possible tableaus is partitioned into a countable collection of disjoint sets (not necessarily open or connected), and on each partition element, the operation is continuous. Two other hypotheses of the theorem are frequently met, but are too technical to state here.What is surprising is the generality of the result, and the fact that the elaborateness of the calculations involved in any given iteration of the algorithm does not affect the result. On the other hand, the result is purely qualitative, and does not indicate the kinds of problems for which the algorithm requires many iterations