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 
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/
@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},
     year = {2008},
     volume = {48},
     number = {9},
     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
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
%U http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_9_a3/
%G ru
%F ZVMMF_2008_48_9_a3

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$.

[1] Skiena S. S., “Who is interested in algorithms and why? – lessons from the Stony Brook algorithms repository”, Sec. Workshop on Algorithm Engng. (WAE'98), Saarbrucken, 1998, 204–212

[2] Kellerer H., Pferschy U., Pisinger D., Knapsack problems, Springer, Berlin, 2004 | MR

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[4] Papadimitriu X., Staiglits K., Kombinatornaya optimizatsiya. Algoritmy i slozhnost, Mir, M., 1985 | MR

[5] Korte B., “Kombinatorische Optimierung und algorithmische Prinzipien”, Okonomische Prognose-, Entscheidungs- und Gleichgewichtsmodelle, VCH Verlagsgesellschaft, Weinheim, 1986, 286–341

[6] Korte B., Vygen J., Combinatorial optimization. Theory and algorithms, 3rd ed., Springer, Berlin, 2006 | MR

[7] Dyubin G. H., Korbut A. A., “Zhadnye algoritmy dlya minimizatsionnoi zadachi o rantse: povedenie v srednem”, Izv. RAN. Teoriya i sistemy upravleniya, 2008, no. 1, 18–28 | MR

[8] Dyubin G. N., Korbut A. A., “Zhadnye algoritmy dlya zadachi o rantse: povedenie v srednem”, Sibirskii zhurnal industr. matem., 2:2(4) (1999), 68–93 | MR | Zbl

[9] Dyubin G. N., Korbut A. A., Sigal I. Kh., “Povedenie v srednem pozhirayuschikh metodov dlya zadachi o rantse – vychislitelnyi eksperiment”, Ekonomiko-matem. issl.: matem. modeli i informatsionnye tekhnol., v. III, Nauka, SPb., 2003, 46–54

[10] Diubin G., Korbut A., “The average behaviour of greedy algorithms for the knapsack problem: General distributions”, Math. Meth. Operat. Res., 57:3 (2003), 449–479 | MR | Zbl

[11] Korbut A. A., Dyubin G. H., Bogolyubov I. H., Vorontsova I. P., “Konkursnyi otbor proektov v regionalnom strategicheskom planirovanii: matematicheskaya i instrumentalnaya podderzhka”, Ekonomika Severo-Zapada: probl. i perspektivy razvitiya, 2006, no. 3(29), 11–18

[12] Korbut A. A., “Kharakterizatsiya dvoistvennykh pozhirayuschikh algoritmov na sistemakh nezavisimosti”, Ekonomiko-matem. issl.: matem. modeli i informatsionnye tekhnol., Nauka, SPb., 2000, 42–51

[13] Sigal I. Kh., Ivanova A. P., Vvedenie v prikladnoe diskretnoe programmirovanie, Fizmatlit, M., 2007