AN ALGORITHM FOR COMPUTING MAXIMUM SOLUTION BASES

被引：5

作者：

HASSIN, R

机构：

[1] Statistics Department, Tel-Aviv University, Tel-Aviv

来源：

OPERATIONS RESEARCH LETTERS | 1990年 / 9卷 / 05期

关键词：

combinatorics; computational complexity; flow algorithms;

D O I：

10.1016/0167-6377(90)90025-Z

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We consider a family of problems defined on a common solution space. A problem is characterized by a subset of the solution space whose elements are defined to be feasible for that problem. Each solution is associated with a cost. Solving a problem means finding a feasible solution of minimum cost. It is assumed that an algorithm for solving any single problem is available. We show how to solve all of the problems in the family by selecting and solving a small subset of them. © 1990.

引用

页码：315 / 318

页数：4

共 10 条

[1]

CHENG CK, 1988, CS88141 U CAL DEP CO

[2]

CHENG CK, IN PRESS ANN OPER RE

[3]

EAVES BC, SOL8513 STANF U DEP

[4] MULTI-TERMINAL NETWORK FLOWS [J].

GOMORY, RE ;

HU, TC .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1961, 9 (04) :551-570

[5] MULTITERMINAL MAXIMUM FLOWS IN NODE-CAPACITATED NETWORKS [J].

GRANOT, F ;

HASSIN, R .

DISCRETE APPLIED MATHEMATICS, 1986, 13 (2-3) :157-163

[6]

GUSFIELD D, 1989, CSE895 U CAL COMP SC

[7]

GUSFIELD D, 1988, EXTRACTING MAXIMAL I

[8]

GUSFIELD D, 1989, SIAM J COMPUT, V19, P143

[9] SOLUTION BASES OF MULTITERMINAL CUT PROBLEMS [J].

HASSIN, R .

MATHEMATICS OF OPERATIONS RESEARCH, 1988, 13 (04) :535-542

[10]

HASSIN R, 1989, IN PRESS ANN OPER RE

← 1 →