# LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?

Given any Integer Linear Program (ILP) there are 2 ways to approximate it:

1. Write down ILP, convert to LP by relaxing the integer constraints and round the solution
2. 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?

• Is it really true that dual relaxation "is considered better" and is "the preferred way" ? What about primal-dual schemes that aren't relaxations per se ? Feb 11 '13 at 4:46
• I wonder what you really mean by "the dual of an ILP" and "solving the dual by relaxing it." Also, I couldn't find Subset Sum solved by these methods in Vazirani's approximation algorithms book. Please give me more specific pointers. Feb 11 '13 at 14:17
• "Write down the ILP, write it's dual and solve dual by relaxing it." This seems technically incorrect to me. First, the ILP has no dual. It's the relaxation of the ILP (an LP) that has a dual. Second, one does not relax that dual (it's already an LP, and does not need to be relaxed to be solved)... Feb 11 '13 at 16:58
• If one uses an ILP formulation and its LP relaxation then clearly it does not hurt to look at the dual. In many cases the dual helps to understand/interpret the lower/upper bound that the relaxations give. This can be exploited algorithmically in a direct fashion, or some times indirectly to provide intuition. Several classical combinatorial optimization results are based on min-max results where duality based analysis/interpretation is very direct and useful. Feb 11 '13 at 22:52
• @ChandraChekuri I think this is the answer the OP is looking for. maybe make it an answer ? Feb 11 '13 at 23:03

• Several classical combinatorial optimization results are based on min-max results where duality based analysis/interpretation is very direct and useful. - Care to elaborate a bit please? Examples?