0
$\begingroup$

Are there approximation algorithms that use primal-dual with LP values and/or rounding?

e.g. An algorithm that during any iteration first tries to see an extreme point to the LP has any value above a given threshold and if so rounds that, otherwise following primal-dual, increments some set of dual variables until some primal variable becomes tight ...
and applies a standard reverse deletion step at the end.

Alternatively are there algorithms that during any iteration first looks at the optimal primal/dual solution and then based on the optimal solution values the primal-dual algorithm increments some set of dual variables until some primal variable becomes tight ... and applies a standard reverse deletion step at the end.

$\endgroup$
1
  • 1
    $\begingroup$ Jain's 2-approximation algorithm for Generalized Steiner Network technically meets the description in your first paragraph. It finds a coordinate of value at least 1/2 in the optimal solution (which always exists --- this is the key insight) and rounds it up to 1, then recurses on the induced problem. $\endgroup$ – Neal Young Jan 31 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.