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

Egon Balas; Liqun Qi

doi:10.1016/0166-218X(93)90164-J

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

Egon Balas, Liqun Qi

Research output: Journal article publication › Journal article › Academic research › peer-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 language	English
Pages (from-to)	1-12
Number of pages	12
Journal	Discrete Applied Mathematics
Volume	43
Issue number	1
DOIs	https://doi.org/10.1016/0166-218X(93)90164-J
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

More information

10.1016/0166-218X(93)90164-J

Cite this

@article{4c40804a70104343a748dcd39600613f,

title = "Linear-time separation algorithms for the three-index assignment polytope",

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.",

keywords = "cliques, facets, odd holes, Three-index assignment",

author = "Egon Balas and Liqun Qi",

year = "1993",

month = may,

day = "6",

doi = "10.1016/0166-218X(93)90164-J",

language = "English",

volume = "43",

pages = "1--12",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

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

AU - Balas, Egon

AU - Qi, Liqun

PY - 1993/5/6

Y1 - 1993/5/6

N2 - 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.

AB - 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.

KW - cliques

KW - facets

KW - odd holes

KW - Three-index assignment

UR - http://www.scopus.com/inward/record.url?scp=38249001519&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(93)90164-J

DO - 10.1016/0166-218X(93)90164-J

M3 - Journal article

SN - 0166-218X

VL - 43

SP - 1

EP - 12

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this