Balas and Saltzman identified several classes of facet inducing inequalities for the three-index assignment polytope, and gave O(n4) separation algorithms for two of them. We give O(n3) separation algorithms for these two classes of facets, and also for a third class. Since the three-index assignment problem has n3variables, these algorithms are linear-time and their complexity is best possible.
- odd holes
- Three-index assignment
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics