Suggestions required on approximation algorithm problems

[ChPravin]

Hi

Please give in your ideas and suggestions on the following problems on approximation algorithms:

1)Give an approximation algorithm that takes an instance of the knapsack problem and a positive integer k and returns a packing with an approximation ratio of no more than 1 + 1/k . Your algorithm must run in O(n^(k+1)) time. Prove that both of these bounds (approximation ratio and running time) are met by your algorithm.

2)Suppose we were to modify the knapsack problem to allow
as many copies as we wish of any of the items. Show that the greedy
algorithm yields an approximation ratio of no more than 2 for this variation.

Thanks & Regards,

[vsareddy]

Are you from K-State??