LINEAR-TIME SEPARATION ALGORITHMS FOR THE 3-INDEX ASSIGNMENT POLYTOPE

Authors
BALAS E QI LQ
Citation
E. Balas et Lq. Qi, LINEAR-TIME SEPARATION ALGORITHMS FOR THE 3-INDEX ASSIGNMENT POLYTOPE, Discrete applied mathematics, 43(1), 1993, pp. 1-12
Citations number
9
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
43
Issue
1
Year of publication
1993
Pages
1 - 12
Database
ISI
SICI code
Abstract
Balas and Saltzman identified several classes of facet inducing inequa lities for the three-index assignment polytope, and gave O(n4) separat ion algorithms for two of them. We give O(n3) separation algorithms fo r these two classes of facets, and also for a third class. Since the t hree-index assignment problem has n3 variables, these algorithms are l inear-time and their complexity is best possible.