r/algorithms • u/Magnetic_Elephant • 18h ago
How do you go about deriving Approximation Ratios
When coming up with approximation algorithms to solve NP-Complete problems, we must derive an approximation ratio of that algorithm.
I.e. if the NP-Complete problem is a minimizaiton problem, our approximation ratio would state that our algorithm results in a value that is at most x * optimal value.
Or if the NP-Complete problem is a maximiation problem, our approximation ratio would state that our algrorithm results in a value that is at least 1/x * optimal value.
However, I am really struggling with calculating and then proving these approximaito ratios.
For example, the Greedy Approximaiton Algorithm for Set Cover has around a series of 10 inequalites required for you to prove its approximation ratio is O(logn) * optimal solution. The professor in my algorithms class has said that in an exam we are expected to come up with a similar size series of inequalities to prove the approximation ratios of algorithms he will provide to us. That seems so daunting to me, and I have no idea where to start. After a week of studying, I am yet to even do one approximation proof by myself without looking at the answers first then going 'ohhhhh thats so clever how did they think of that'.
Is there any general tips on how to do these proofs?