A&DS S04E13. Approximation Algorithms

Algorithms and data structures. Semester 4. Lecture 13
In the thirteenth lecture, we discussed approximation algorithms, that is, algorithms that find not an exact solution, but some solution that approximates the optimal one with some accuracy.
ITMO University, 2022

[@omaraljarrah5089]

We would love if we had more of the English content, your content, the way you explain algorithms is just exceptional! Thanks for your hard work!

[@nirajandata]

thanks

[@madhukiranattivilli2321]

Hi Pavel, Dynamic Programming solution to knapsack is O(nW) where n is total # of objects and W is knapsack weight Why is this NP-Complete? It it because, when the knapsack weight W is a very big number, there will be problems with insufficient memory or run time would be very long, even though we would eventually get the solution (represented by "Complete" part in NP-Complete)?

[@pavelmavrin]

Hi! I discuss NP-completeness in this lesson kzbin.info/www/bejne/sJuleWSen6mIf9U In simple words, NP-complete problem is the problem that is proved to be harder than any problem in NP class. So if we solve any NP-complete problem in polynomial time, we will be able to solve all NP problems. For the knapsack problem, O(nW) is not a polynomial time because W is not the size of the input.

[@madhukiranattivilli2321]

@@pavelmavrin Ok, I'll watching the video again. Thankyou!

[@madhukiranattivilli2321]

@@pavelmavrin Understood the difference between "input -- not useful in Big-O computation" vs "size of input" Input value can grow rapidly, size of input need not. I hope I'm making sense!

[@madhukiranattivilli2321]

Hi Pavel, knapsack approx sol ANS = max(Cgreedy, Cmax) >= 0.5 * OPT When it is 0.5OPT solution, why are you calling it 2OPT solution? When you spoke about TSP approx soln, ANS

[@pavelmavrin]

Here I call a solution K-optimal if it differs from the optimal one by no more than K times.

[@madhukiranattivilli2321]

@@pavelmavrin Ok, understood K-optimal not 2-optimal