STOCHASTIC ONLINE KNAPSACK-PROBLEMS

被引：90

作者：

MARCHETTISPACCAMELA, A

VERCELLIS, C

机构：

[1] POLITECN MILAN,DIPARTIMENTO ECON & PROD,I-20133 MILAN,ITALY

[2] UNIV ROMA LA SAPIENZA,DIPARTIMENTO INFORMAT & SISTEMIST,ROME,ITALY

来源：

MATHEMATICAL PROGRAMMING | 1995年 / 68卷 / 01期

关键词：

KNAPSACK PROBLEMS; ONLINE ALGORITHMS; STOCHASTIC INTEGER PROGRAMMING;

D O I：

10.1007/BF01585758

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Different classes of on-line algorithms are developed and analyzed for the solution of {0, 1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value is O(log(3/2) n). An Omega(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.

引用

页码：73 / 104

页数：32

共 19 条

[1]

Breiman L., 1968, PROBABILITY

[2] MULTI-CONSTRAINED MATROIDAL KNAPSACK-PROBLEMS [J].