2 ms·
Given there are no overlapping subproblems, I think greedy is optimal[1]. The point was to show primal I(L)P with dual decomposition. 1. You're right, a counte
by jvanderbot 7y ago
Given there are no overlapping subproblems, I think greedy is optimal[1]. The point was to show primal I(L)P with dual decomposition.
1. You're right, a counter example for greedy (with 2 appox) looks something like: c1=.5+eps, v1=1, c2=.5, v2=.5+eps, B=2.