PROBABILISTIC ANALYSIS OF THE GENERALIZED ASSIGNMENT PROBLEM

被引：17

作者：

DYER, M ^{[1
]}

FRIEZE, A ^{[1
]}

机构：

[1] CARNEGIE MELLON UNIV,DEPT MATH,PITTSBURGH,PA 15213

来源：

MATHEMATICAL PROGRAMMING | 1992年 / 55卷 / 02期

关键词：

PROBABILISTIC ANALYSIS; GENERALIZED ASSIGNMENT;

D O I：

10.1007/BF01581197

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We analyse the generalised assignment problem under the assumption that all coefficients are drawn uniformly and independently from [0, 1]. We show that such problems can be solved exactly with high probability, in a well-defined sense. The results are closely related to earlier work of Lueker, Goldberg and Marchetti-Spaccamela and ourselves.

引用

页码：169 / 181

页数：13

共 8 条

[1] A PROPERTY OF ASSIGNMENT TYPE MIXED INTEGER LINEAR-PROGRAMMING PROBLEMS [J].

BENDERS, JF ;

VANNUNEN, JAEE .

OPERATIONS RESEARCH LETTERS, 1983, 2 (02) :47-52

[2]

DYER ME, 1989, MATH OPER RES, P162

[3]

GOLDBERG AV, 1984, 16TH P ANN ACM S THE, P359

[4] PROBABILITY-INEQUALITIES FOR SUMS OF BOUNDED RANDOM-VARIABLES [J].

HOEFFDING, W .

JOURNAL OF THE AMERICAN STATISTICAL ASSOCIATION, 1963, 58 (301) :13-+

[5]

JORNSTEN KO, 1986, EUROPEAN J OPERATION, P313

[6]

Lueker G.S., 1982, APPL PROBABILITY COM, V1, P489504, DOI [DOI 10.1007/978-1-4612-5791-2, 10.1007/978-1-4612-5791-2_22, DOI 10.1007/978-1-4612-5791-2_22]

[7]

MCDIARMID C, 1989, LOND MATH S, V141, P148

[8] BRANCH AND BOUND ALGORITHM FOR GENERALIZED ASSIGNMENT PROBLEM [J].

ROSS, GT ;

SOLAND, RM .

MATHEMATICAL PROGRAMMING, 1975, 8 (01) :91-103

← 1 →