| Article ID: | iaor20091415 |
| Country: | Netherlands |
| Volume: | 5 |
| Issue: | 2 |
| Start Page Number: | 541 |
| End Page Number: | 549 |
| Publication Date: | May 2008 |
| Journal: | Discrete Optimization |
| Authors: | Tovey Craig A., Johnson Ellis L., Hunsaker Brady |
We exhibit a polar relationship between two measures that have been proposed to evaluate the importance of TSP facets, the Kuhn–Gomory shooting experiment size and the probability of integrality in an augmented LP relaxation. The polarity establishes the complexity of performing the shooting experiment. We illustrate the resulting relationship on the Chinese postman and minimum spanning set problems.