-2
$\begingroup$

I have an assignment problem-like structure with a bunch of additional constraints formulated as an integer linear program. By relaxing the integral constraint I ended up in a relaxed LP problem for which I want to develop a greedy rounding technique. Is there any reference for such ''greedy rounding'' approach and a template to go with ?

Improve this question
$\endgroup$
1
  • $\begingroup$ Most (provably good) approximation algorithms based on rounding relaxed LPs use randomized rounding, not greedy rounding. Most greedy algorithms are not rounding algorithms. So there is no "template" of the kind you ask for, really. But you can greedily round the standard relaxed LP for vertex cover to get a 2-approximation. A more sophisticated example that comes to mind is Jain's 2-approximation for degree-constrained spanning tree, e.g. scholar.google.com/… $\endgroup$
    – Neal Young
    Nov 21 at 17:17

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.