Given any Integer Linear Program (ILP) there are 2 ways to approximate it:
- Write down ILP, convert to LP by relaxing the integer constraints and round the solution
- Write down the ILP, convert to LP by relaxing the integer constraints, write it's dual and solve it
Why is the second approach considered 'better'? What makes it the preferred way of approximating the solution to an ILP? What is that #2 has that #1 doesn't?
In Vazirani's Approximation Algorithms book he approximates set cover using both of the methods above, but I'm unable to discern the underlying concept of choosing #2 over #1? What "IS" the intuitive 'aha' to help me understand this?