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

被引：12

作者：

BALAS, E ^{[1
]}

QI, LQ ^{[1
]}

机构：

[1] UNIV NEW S WALES,SCH MATH,KENSINGTON,NSW 2033,AUSTRALIA

来源：

DISCRETE APPLIED MATHEMATICS | 1993年 / 43卷 / 01期

基金：

澳大利亚研究理事会; 美国国家科学基金会;

关键词：

3-INDEX ASSIGNMENT; FACETS; CLIQUES; ODD HOLES;

D O I：

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

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 n3 variables, these algorithms are linear-time and their complexity is best possible.

引用

页码：1 / 12

页数：12

共 9 条

[1]

[Anonymous], 1967, CORS J

[2] AN ALGORITHM FOR THE 3-INDEX ASSIGNMENT PROBLEM [J].

BALAS, E ;

SALTZMAN, MJ .

OPERATIONS RESEARCH, 1991, 39 (01) :150-161

[3] FACETS OF THE 3-INDEX ASSIGNMENT POLYTOPE [J].

BALAS, E ;

SALTZMAN, MJ .

DISCRETE APPLIED MATHEMATICS, 1989, 23 (03) :201-229

[4]

BALAS E, 1990, 9019 U NEW S WAL SCH

[5] AN ALGORITHM FOR SOLVING 3-DIMENSIONAL ASSIGNMENT PROBLEMS WITH APPLICATION TO SCHEDULING A TEACHING PRACTICE [J].

FRIEZE, AM ;

YADEGAR, J .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1981, 32 (11) :989-995

[6] COMPLEXITY OF A 3-DIMENSIONAL ASSIGNMENT PROBLEM [J].

FRIEZE, AM .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1983, 13 (02) :161-164

[7]

HANSEN P, 1973, CAHIERS CTR ETUDES R, V15, P327

[8]

LEUE O, 1972, ANGEW INFORM, P154

[9] MULTIDIMENSIONAL ASSIGNMENT PROBLEM [J].

PIERSKALLA, WP .

OPERATIONS RESEARCH, 1968, 16 (02) :422-+

← 1 →