Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite

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?

share|improve this question
3  
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 ? – Suresh Venkat♦ Feb 11 at 4:46
3  
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. – Yoshio Okamoto Feb 11 at 14:17
4  
"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)... – Neal Young Feb 11 at 16:58
5  
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. – Chandra Chekuri Feb 11 at 22:52
2  
@ChandraChekuri I think this is the answer the OP is looking for. maybe make it an answer ? – Suresh Venkat♦ Feb 11 at 23:03
show 9 more comments

1 Answer

up vote 4 down vote accepted

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.

Making the comment an answer based on Suresh's suggestion.

share|improve this answer
2  
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? – PhD Feb 12 at 8:46
4  
@PhD: If you need elaboration here, I'd recommend to learn basic combinatorial optimization first before learning approximation algorithms. You can consult a book by Korte and Vygen, or Cook, Cunningham, Pulleyblank, and Schrijver, or Papadimitriou and Steiglitz, for example. – Yoshio Okamoto Feb 12 at 14:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.