0
$\begingroup$

I am attempting to figure out how to use approximation factors to determine the answers an algorithm can return for graph problems.

For example, if a graph G actually has a maximum clique with 13 vertices, and we use a 1.5-approximation algorithm to approximate the maximum clique - what is the minimum size clique that can be returned by this algorithm?

My first thought was to simply divide 13 / 1.5 since this would represent the worst that the algorithm could do. However, since that is ~ 8.6, would the minimum the algorithm returns be 9 or 8?

$\endgroup$
1
$\begingroup$

An approximation algorithm for a maximization algorithm has an approximation ratio of $\alpha \geq 1$ if whenever the true answer is $m$, the algorithm is promised to return a solution with value at least $m/\alpha$.

In your case, $m = 13$ and $\alpha = 1.5$, and so by definition, the algorithm must return a clique whose size is at least $13/1.5$. Since the size of the clique is an integer, if a clique is of size at least $13/1.5 \approx 8.6$, then it is in fact at least $\underline{\quad}$ (fill in the blanks).

$\endgroup$
  • $\begingroup$ Since it is at LEAST 8.6, than means it cannot be 8 and therefore must be 9? $\endgroup$ – foobarbaz Apr 28 '18 at 19:17
  • $\begingroup$ Exactly. That's correct. $\endgroup$ – Yuval Filmus Apr 28 '18 at 19:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.