<p>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. </p>

<p>Making the comment an answer based on Suresh's suggestion.</p>

CC BY-SA 3.0
2013-02-12T08:46:05.187Z
`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
CC BY-SA 3.0
2013-02-12T14:19:37.227Z
@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
CC BY-SA 3.0
2013-02-12T05:57:19.957Z
2013-02-12T05:57:19.957Z
Chandra Chekuri
<p>Given any Integer Linear Program (ILP) there are 2 ways to approximate it:</p>

<ol>
<li>Write down ILP, convert to LP by relaxing the integer constraints and round the solution</li>
<li>Write down the ILP, convert to LP by relaxing the integer constraints, write it's dual and solve it</li>
</ol>

<p>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?</p>

<p>In Vazirani's Approximation Algorithms book he approximates <strong>set cover</strong> 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?</p>

CC BY-SA 3.0
2013-02-11T03:14:46.153Z
For me, the power of #2 is that is often gives more insight into the combinatorial structure of the problem. By relaxing the dual and using that in primal-dual greedy algorithm we gain more knowledge about the "feel" of the problem. With randomized rounding that intuition is less often there.
Nicholas Mancuso
CC BY-SA 3.0
2013-02-11T04:46:03.487Z
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
CC BY-SA 3.0
2013-02-11T04:55:36.210Z
@SureshVenkat - I'd appreciate some more light on that. I'm not really familiar with that part (yet to reach it :)
PhD
CC BY-SA 3.0
2013-02-11T07:34:48.850Z
I'm trying to question the premise of your question itself.
Suresh Venkat
CC BY-SA 3.0
2013-02-11T14:17:09.577Z
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
CC BY-SA 3.0
2013-02-11T16:32:02.370Z
@YoshioOkamoto, Vazirani applies both of these methods for set cover. Perhaps OP should edit?
Nicholas Mancuso
CC BY-SA 3.0
2013-02-11T16:58:39.757Z
"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
CC BY-SA 3.0
2013-02-11T17:08:08.713Z
My sense is that randomized rounding is generally more powerful than primal-dual.  But It would be interesting to survey the literature to see.  Also, FWIW, you can view some primal-dual approximation algorithms (e.g. greedy set cover and Lagrangian-relaxation algorithms for packing and covering) as randomized-rounding algorithms (derandomized via the method of conditional probabilities).  In this way, the two techniques are sometimes technically related.
Neal Young
CC BY-SA 3.0
2013-02-11T17:20:16.913Z
@NealYoung I think the OP didn't realize that "relax" and "dualize" don't commute :)
Suresh Venkat
CC BY-SA 3.0
2013-02-11T21:57:06.810Z
Fixed the question to address the concerns.
PhD
CC BY-SA 3.0
2013-02-11T22:52:07.757Z
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
CC BY-SA 3.0
2013-02-11T23:03:48.267Z
@ChandraChekuri I think this is the answer the OP is looking for. maybe make it an answer ?
Suresh Venkat
CC BY-SA 3.0
2013-02-11T23:48:18.343Z
I still fail to understand what the question is.  Solving the primal of LP and solving the dual of LP are the same thing.  Therefore, option 1 is more precisely written as “solve LP relaxation and round the primal solution.”  This looks fine.  But option 2 is just “solve LP relaxation and do something to the dual solution.”  Do _what_?
Tsuyoshi Ito
CC BY-SA 3.0
2013-02-12T00:11:34.610Z
To me, it's not yet clear if #2 means primal-dual methods although some comments assumed so.
Yoshio Okamoto
<approximation-algorithms><linear-programming><primal-dual>
LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?
PhD
# LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?

(Asked by: username_0 on 2013-02-10)

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?

**Tags:** approximation-algorithms, linear-programming, primal-dual

> **Comments:**
> **username_1**: For me, the power of #2 is that is often gives more insight into the combinatorial structure of the problem. By relaxing the dual and using that in primal-dual greedy algorithm we gain more knowledge about the "feel" of the problem. With randomized rounding that intuition is less often there.  
> **username_2**: 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 ?  
> **username_0**: @SureshVenkat - I'd appreciate some more light on that. I'm not really familiar with that part (yet to reach it :)  
> **username_2**: I'm trying to question the premise of your question itself.  
> **username_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.  
> **username_1**: @YoshioOkamoto, Vazirani applies both of these methods for set cover. Perhaps OP should edit?  
> **username_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)...  
> **username_4**: My sense is that randomized rounding is generally more powerful than primal-dual.  But It would be interesting to survey the literature to see.  Also, FWIW, you can view some primal-dual approximation algorithms (e.g. greedy set cover and Lagrangian-relaxation algorithms for packing and covering) as randomized-rounding algorithms (derandomized via the method of conditional probabilities).  In this way, the two techniques are sometimes technically related.  
> **username_2**: @NealYoung I think the OP didn't realize that "relax" and "dualize" don't commute :)  
> **username_0**: Fixed the question to address the concerns.  
> **username_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.  
> **username_2**: @ChandraChekuri I think this is the answer the OP is looking for. maybe make it an answer ?  
> **username_6**: I still fail to understand what the question is.  Solving the primal of LP and solving the dual of LP are the same thing.  Therefore, option 1 is more precisely written as “solve LP relaxation and round the primal solution.”  This looks fine.  But option 2 is just “solve LP relaxation and do something to the dual solution.”  Do _what_?  
> **username_3**: To me, it's not yet clear if #2 means primal-dual methods although some comments assumed so.  

---

## 1 answers

### Answer by username_5 on 2013-02-12. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: `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?  
> **username_3**: @username_0: 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.  

---

