What is Approximation Algorithm?
Sometime people will ask what did I learn from my graduate program, and most of them were curious about approximation algorithms. So, what can approximation algorithms help us during our normal life? I’m going to use the knapsack problem for an example, which is also a well-defined optimization problem. This problem often happens normally in people’s life.
Imagine we are now a purchasing agent entering the most popular outlet. Our way to earn money is to buy things with the price after the discount and then sale it to comsumers with their origninal price. So, since with limited time and limited capacity, what strategy should we use to maximize our profit?
People now will say, it’s easy to figure it out, just try everything. This is totally unrealistic, since the combinations will be thousands or even millions of it if you do so.
Surpisingly, a simple approximation algorithm or you can say it just a simple strategy that can easily garuantee your profit in promising time. In other words, if the optimal is to earn 100,000 dollars, some approximation algorithms can garuantee you earn at least 50,000 dollars or even better in a much shorter time.
Greedy algorithm for the Knapsack problem
Down below we are going to show an approximation algorithm that can garuantee the result will be at least 1/2 optimal, and it is definitely not difficult to think of this method.
Assume that we have targeted n items that we are willing to buy. Also, intuitively, our bag can easily fit any item alone, or else it make no sence carrying a futile bag. Then we easily labeled the n items with the money we can earn and its size. For instance, picking Product A, can let us earn 500 dollars and it cost 1L of our bag (+500, 1L), Product B (+5000, 3L), and so on. Now, we have to make the decision, and our first thought is to rank all the items. But how? In what aspect can we ensure picking Product B at this moment will be better than Product A? Cost-performance then come out in our mind, which we can show the value per space cost of all the items.
We set this idea with expression P, P1 represent product 1 with (Value 1 / Space Cost 1), and set them in decreasing arrangement for all n items.
P1 = (V1/S1), P2 = (V2/S2), P3= (V3/S3) …, P1 > P2 > P3 … > Pn
Then we try to be GREEDY. Accordingly, we try to fill up our bag. So, the first k-1 items will be picked into the bag, since they have better performance. (With k ≤ n, and k-1 will be the last product that is able to fit into the bag)
It’s seems like we have done a great job, and it is time to go home. However, something went wrong, after we realize that Pk has a larger value than all the things we took. As a result, we timely correct our decision, pick only Pk, instead of the orginal k-1 items. Lastly, this result have been proved, by the picking stategy, we’ll ensure the value as at least 1/2 optimal.
To sum up, approximation algorithms giving us a chance to use the “stategy” to come close to our goal. There are also many cool algorithms not only interesting but also very useful to our normal life.
Thanks for reading! If you liked this, click the clap below so other people will see this here on Medium.
