Opgaven W12 1. Het BIN PACKING probleem is als volgt gedefini¨eerd: Gegeven: n items met grootte a1 , a2 , ..., an ≤ 1 Gevraagd: Wat is het minimale aantal bins ter grootte 1 dat nodig is om de n items in te pakken? Beschouw het volgende algoritme: FIRST FIT: • Beschouw de items in willekeurige volgorde • Voeg item toe aan eerste bin waarin het past. Als item in geen enkele bin past, open een nieuwe bin Laat zien dit het algoritme FIRST FIT een 2-approximatiealgoritme voor BIN PACKING is. 2. Beschouw het knapsackprobleem z = max n X cj xj , odv j=1 n X aj xj ≤ b, x ∈ Z≥0 . j=1 Veronderstel dat: aj ≤ b, j = 1, . . . , n aj ∈ Z≥0 , j = 1, . . . , n b ∈ Z≥0 cj c1 ≥ , j = 2, . . . , n . a1 aj De “greedyoplossing” voor dit probleem is (xG )T = (b(b/a1 )c, 0, . . . , 0) met waarde z G = c1 b(b/a1 )c. Laat zien dat z G ≥ (1/2)z. Hint: De optimale oplossing van de LP-relaxatie, gegeven de aannames, is: (xLP )T = ((b/a1 ), 0, . . . , 0) met waarde zLP = c1 (b/a1 ). Bovendien weten we dat z G ≤ z ≤ zLP , en daardoor dat z G /z ≥ z G /zLP . Laat nu zien dat z G /zLP ≥ 1/2. 1
© Copyright 2024 ExpyDoc
