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

Egon Balas, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

17 Citations (Scopus)

Abstract

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
Volume43
Issue number1
DOIs
Publication statusPublished - 6 May 1993
Externally publishedYes

Keywords

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

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this