For the dual complementary slackness conditions we can see that these are 2-relaxed because for every edge e either y(e) is equal 0 or in the worse case both end points have variable set 1.
| The analysis
is very simple because we can easily see that the primal complementary slackness
conditions hold since for every vertex u either the variable x(u)
is equal 0 or the constraint for vertex u is tight. So the sum of
y(e) for all the edges incident to u is equal to w. For the dual complementary slackness conditions we can see that these are 2-relaxed because for every edge e either y(e) is equal 0 or in the worse case both end points have variable set 1. |
|
