
doi: 10.1007/bf01582230
This is an important paper, with a number of highly significant results. The issues surround integer linear programs with fixed coefficient matrices, and varying objective functions and right-hand side vectors. This work strengthens, implies, generalizes and/or strongly relates to work by Blair and Jeroslow, Graver, Wolsey, Gomory, von zur Gathen and Sieveking, Karp and Papadimitriou, Schrijver, Chvátal, Hoffman and Kruskal, Lenstra, Hoffman, and a host of others, and basic references would include Stoer and Witzgall. The effort has significant material on every page, but the authors single out for mention in their abstract the following: for any optimal solution to a linear program (obtained from the integer program), the distance to the nearest optimal solution to the integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral coefficient matrix A, and the Chvátal rank of the polyhedron \(\{\) \(x| Ax\leq b\}\) can be bounded above by a function of A, independent of b. They also show, among many other results, that the Blair-Jeroslow theorem (on Gomory functions) is equivalent to each rational matrix having finite Chvátal rank. Anyone with any interest in the subject area should read this paper, but the reviewer is sure they already have.
fixed coefficient matrices, nearest optimal solution, Linear programming, Sensitivity, stability, parametric optimization, Chvátal rank, Integer programming, varying objective functions
fixed coefficient matrices, nearest optimal solution, Linear programming, Sensitivity, stability, parametric optimization, Chvátal rank, Integer programming, varying objective functions
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 138 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 1% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
