Balas and Saltzman identified several classes of facet inducing inequalities forthe three-index assignment polytope, and gave O(n to the 4th power) separation algorithms for two of them. We give O(n cubed) separation algorithms for these two classes of facets, and also for a third class. Since the three-index assignment problem has n cubed variables, these algorithms are linear-time and their complexity is best possible. (kr)
展开▼
