On Algorithms for Discrete Problems.
Abstract
The 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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1973
- Accession Number
- AD0761071
Entities
People
- Robert G. Jeroslow
Organizations
- Carnegie Mellon University