A lot of approximation algorithms are based on relaxation. The way it usually works is this. You take the original problem and relax it some large class of efficiently solvable problem (e.g. relax an IP to an LP). Any solution to the original problem of cost $X$ gives a corresponding solution to the relaxation of cost $X$.

You then convert a solution to the relaxed problem of cost $Y$ to a solution to the original problem of cost $\alpha Y$ for some $\alpha > 1$. This implies that you have an $\alpha$ approximation.

But what if you could argue that the original feasible solution of cost $X$ guarantees the existence of a solution to the relaxation of cost $X/\beta$? Then you would get an $\alpha/\beta$ approximation algorithm.

Has this strategy ever been employed? Is there ever a case when you can show that a feasible solution to the original problem corresponds to a feasible solution to the relaxation of strictly lower cost ?

  • 4
    $\begingroup$ If there is a $\beta$ for the relaxation you have in mind then why not work with tighter relaxation obtained by scaling up the solution of the relaxation by $\beta$? There are examples where one uses more than one relaxation and argues that not both of them can behave in the worst case way for any given instance and one can leverage this to get a better approximation than using only one. $\endgroup$ – Chandra Chekuri Feb 9 '12 at 22:38
  • 1
    $\begingroup$ @Chandra: I think that the first sentence in your comment is the answer to the question. Can you post it as an answer? Another option is to close this question (but in that case, the reason for closing is unclear to me—maybe we need another close reason called “forehead-slapper”). $\endgroup$ – Tsuyoshi Ito Feb 14 '12 at 19:08

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.