Linear-time separation algorithms for the three-index assignment polytope

Egon Balas, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

13 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)1-12
Number of pages12
JournalDiscrete Applied Mathematics
Issue number1
Publication statusPublished - 6 May 1993
Externally publishedYes


  • cliques
  • facets
  • odd holes
  • Three-index assignment

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Linear-time separation algorithms for the three-index assignment polytope'. Together they form a unique fingerprint.

Cite this