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 language | English |
|---|---|
| Pages (from-to) | 1-12 |
| Number of pages | 12 |
| Journal | Discrete Applied Mathematics |
| Volume | 43 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 6 May 1993 |
| Externally published | Yes |
Keywords
- cliques
- facets
- odd holes
- Three-index assignment
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics
Fingerprint
Dive into the research topics of 'Linear-time separation algorithms for the three-index assignment polytope'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver