Authors
Citation
A. Marchettispaccamela et C. Vercellis, STOCHASTIC ONLINE KNAPSACK-PROBLEMS, Mathematical programming, 68(1), 1995, pp. 73-104
Citations number
19
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
ISSN journal
00255610
Volume
68
Issue
1
Year of publication
1995
Pages
73 - 104
Database
ISI
SICI code
0025-5610(1995)68:1<73:SOK>2.0.ZU;2-I
Abstract
Different classes of on-line algorithms are developed and analyzed for
the solution of {0, 1} and relaxed stochastic knapsack problems, in w
hich both profit and size coefficients are random variables. In partic
ular, a linear time on-line algorithm is proposed for which the expect
ed difference between the optimum and the approximate solution value i
s O(log(3/2) n). An Omega(1) lower bound on the expected difference be
tween the optimum and the solution found by any on-line algorithm is a
lso shown to hold.