Hi,

I am trying to understand the FPTAS for the knapsack problem. I have got the following from wikepedia:

 

I have following questions:

 

(a)It shows two 2 ‘k’ symbols. I can’t understand the difference between them.

(b)Why its dividing the value  v_i with the value of ‘K’ which is a ratio of P/n multiply by epsilon

(c)what is the significance of Epsilon?

(d)why rounding would convert the problem into a polynomial time problem?

 

Somebody please guide me.

 

Zulfi.

11 hours ago, zak100 said:

Hi,

I am trying to understand the FPTAS for the knapsack problem. I have got the following from wikepedia:

 

I have following questions:

(a)It shows two 2 ‘k’ symbols. I can’t understand the difference between them.

(b)Why its dividing the value  v_i with the value of ‘K’ which is a ratio of P/n multiply by epsilon

(c)what is the significance of Epsilon?

(d)why rounding would convert the problem into a polynomial time problem?

Hi again Zulfi!

(a) It is the same K, only the author used different typesetting, first for a K in normal text font, second with a K in math font.

(b) It makes the new value \(v_i'\) into a whole number value that is large (if \(\varepsilon\) is small) compared to the original real-valued \(v_i\).

(c) If \(\varepsilon\) is small, then the new  \(v_i'\) is big, and its size tells you about the size of \(v_i\) relative to the average \(P/n\) of all the different sizes.

(d) On https://en.wikipedia.org/wiki/Knapsack_problem you also have the dynamic programming algorithms that solve the problem in polynomial time for the new rounded weights.