2
$\begingroup$

From wikipedia:

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a $ρ$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $ρ$ times the value, OPT, of an optimum solution.

$$\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}$$

For a maximization problem, a $\rho$-approximation algorithm means that, for an instance $x$, $\rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT}$, for any $\rho<1$. Is this mean that in the worst case the algorithm produces a solution that is at least $\rho \mathrm{OPT}$? Or is this in the average case? Because there are some instances where the algorithm find the optimal solution.

I mean, if the algorithm is executed, say $10000$ times (with randomly generated instances) and produces $\mathrm{OPT}$, say $9995$ times and $5$ times it produces a value that is greater than $\rho\mathrm{OPT}$. What can we say about the algorithm then?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

It's a worst case guarantee. It can in some cases do better than $\rho OPT$, but it will never do worse.

In your example we can say very little about the algorithm since you've only tested it with relatively few random instances of a given size. On non-random (structured) inputs it might perform much worse.

Improve this answer
$\endgroup$
0
$\begingroup$

It is the worst case. $\rho$ can be one sided bound as in examples you provided or bounded on both sides (example is in next paragraph on wikipedia).

This might be the case $$\mathrm(OPT - c) \leq f(x) \leq \mathrm(OPT + c)$$ But still it might be bounded on one side but situation you have is due to roundoff problems of floating point values.

Unfortunatelly we cannot assume anything about algorithm when given finite number of instances.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I can't understand your answer. What's alpha? $\endgroup$
    – David Richerby
    Commented Jul 30, 2015 at 19:17
  • 1
    $\begingroup$ Please edit your answer to use the same notation as in the question, which calls the approximation factor $\rho$ (rho). Also, you can use LaTeX for mathematics. $\endgroup$
    – David Richerby
    Commented Jul 30, 2015 at 19:28

Your Answer

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

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