Set cover איך בדיוק מוכיחים שהחסם על האלג' החמדני המקרב ב Set Cover הוא ln(n) + 1 ?
W W12X New member 23/4/08 #1 Set cover איך בדיוק מוכיחים שהחסם על האלג' החמדני המקרב ב Set Cover הוא ln + 1 ?
1 1ca1 New member 23/4/08 #4 קשה לגגל? http://www-math.mit.edu/~goemans/18434/setcover-tamara.pdf בכל מקרה, אני בטוח שזה מופיע בספר של ואזיריאני (וגם כנראה קורמן, ואני אופתע מאוד אם לא מופיע גם בקליינברג, בקיצור כל ספר על אלגוריתמים או אלגוריתמי קירוב).
קשה לגגל? http://www-math.mit.edu/~goemans/18434/setcover-tamara.pdf בכל מקרה, אני בטוח שזה מופיע בספר של ואזיריאני (וגם כנראה קורמן, ואני אופתע מאוד אם לא מופיע גם בקליינברג, בקיצור כל ספר על אלגוריתמים או אלגוריתמי קירוב).
1 1ca1 New member 23/4/08 #5 כאן יש הוכחה קלה יותר http://www-math.mit.edu/~goemans/18434/setcover-daniel.pdf הכל נהיה פשוט יותר כאשר עוברים לLP.
כאן יש הוכחה קלה יותר http://www-math.mit.edu/~goemans/18434/setcover-daniel.pdf הכל נהיה פשוט יותר כאשר עוברים לLP.
+ 1 ?