COMP4600/8460 - Advanced Algorithms S2 2022 Assignment 2

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP4600/8460 - Advanced Algorithms

S2 2022

Assignment 2

1    Questions

Q1)  Prove Strong Duality Theorem (5 Marks)

Q2) Implement primal-dual algorithm APDsetcover  in Python/Java/C. Evaluate the approximation ratio on random SetCover instances, and compare the approximation ratio with greedy algorithm Asetcover . To generate a random SetCover instance, you may assign a cost to each cover by a uniform probability distribution, and make each item coverable by a particular cover with a probability = 0.5.  Plot and discuss the results of approximation ratios here in this report, and upload your code separately on Wattle (10 Marks)

Q3)  Show 3SAT ⪯ SubsetSum ⪯ Knapsack (10 Marks)

Q4)  Study BinPacking problem:

Q4.1)  Show that there is a 2-approximation for BinPacking (5 Marks)

Q4.2)  Show that there is no (  − e)-approximation for BinPacking (5 Marks)

2    Answers

...

References

[Vazirani]    V . Vazirani, Approximation Algorithms, Springer, (2003).