GRAPH-THEORETIC RELAXATIONS OF SET COVERING AND SET PARTITIONING PROBLEMS

被引：16

作者：

ELDARZI, E

MITRA, G

机构：

[1] BRUNEL UNIV,DEPT MATH & STAT,UXBRIDGE UB8 3PH,MIDDX,ENGLAND

[2] UNIV WESTMINSTER,DIV MATH & DECIS SCI,LONDON,ENGLAND

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1995年 / 87卷 / 01期

关键词：

SET COVERING; SET PARTITIONING; NETWORK; ASSIGNMENT; SHORTEST ROUTE; SPANNING TREE;

D O I：

10.1016/0377-2217(94)00115-S

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper we review the graph theoretic relaxations of the set covering problem (SCP) and the set partitioning problem (SSP). These are: a network relaxation which can be solved by the greedy method, a matching relaxation and a graph covering relaxation. Other relaxations such as assignment, shortest route and minimum spanning tree are also presented.

引用

页码：109 / 121

页数：13

共 44 条

[1] A NETWORK RELAXATION BASED ENUMERATION ALGORITHM FOR SET PARTITIONING [J].

ALI, AI ;

THIAGARAJAN, H .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 38 (01) :76-85

[2]

[Anonymous], 1990, MODEL BUILDING MATH

[3]

Arabeyre J.P., 1969, TRANSPORTATION SCI, V3, P140, DOI 10.1287/trsc.3.2.140

[4] COMPUTATIONAL RESULTS FOR VERY LARGE AIR CREW SCHEDULING PROBLEMS [J].

BAKER, E ;

FISHER, M .

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1981, 9 (06) :613-618

[5]

BALAS E, 1980, MATH PROGRAM STUD, V12, P37, DOI 10.1007/BFb0120886

[6] SET PARTITIONING - SURVEY [J].

BALAS, E ;

PADBERG, MW .

SIAM REVIEW, 1976, 18 (04) :710-760

[7]

BALAS E, 1983, REV BELGE STAT INFOR, V22, P36

[8]

BALINSKI ML, 1970, P PRINCETON S MATH P

[9]

BEASLEY JE, 1990, NAV RES LOG, V37, P151, DOI 10.1002/1520-6750(199002)37:1<151::AID-NAV3220370110>3.0.CO

[10]

2-2

← 1 2 3 4 5 →