Geodesic
Average behavior of greedy algorithms for the minimization knapsack problem: General coefficient distributions
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 9, pp. 1556-1570

Voir la notice de l'article provenant de la source Math-Net.Ru

For the minimization knapsack problem with Boolean variables, primal and dual greedy algorithms are formally described. Their relations to the corresponding algorithms for the maximization knapsack problem are shown. The average behavior of primal and dual algorithms for the minimization problem is analyzed. It is assumed that the coefficients of the objective function and the constraint are independent identically distributed random variables on $[0,1]$ with an arbitrary distribution having a density and that the right-hand side $d$ is deterministic and proportional to the number of variables (i.e., $d=\mu n$). A condition on $\mu$ is found under which the primal and dual greedy algorithms have an asymptotic error of $t$. 
@article{ZVMMF_2008_48_9_a3,
     author = {G. N. Dyubin and A. A. Korbut},
     title = {Average behavior of greedy algorithms for the minimization knapsack problem: {General} coefficient distributions},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {1556--1570},
     publisher = {mathdoc},
     volume = {48},
     number = {9},
     year = {2008},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_9_a3/}
}
TY  - JOUR
AU  - G. N. Dyubin
AU  - A. A. Korbut
TI  - Average behavior of greedy algorithms for the minimization knapsack problem: General coefficient distributions
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2008
SP  - 1556
EP  - 1570
VL  - 48
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_9_a3/
LA  - ru
ID  - ZVMMF_2008_48_9_a3
ER  - 
%0 Journal Article
%A G. N. Dyubin
%A A. A. Korbut
%T Average behavior of greedy algorithms for the minimization knapsack problem: General coefficient distributions
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2008
%P 1556-1570
%V 48
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_9_a3/
%G ru
%F ZVMMF_2008_48_9_a3
G. N. Dyubin; A. A. Korbut. Average behavior of greedy algorithms for the minimization knapsack problem: General coefficient distributions. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 9, pp. 1556-1570. http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_9_a3/