| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141860 | Discrete Optimization | 2008 | 9 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Brady Hunsaker, Ellis L. Johnson, Craig A. Tovey,