2
$\begingroup$

It seems like the consensus is to define an $\alpha$-competitive algorithm if $\mathbb{E}_R(ALG) \geq \alpha \mathbb{E}_R(OPT)$ where $\mathbb{E}_R$ is the expected value taken across the problem instances.

I am wondering why the more natural definition of $\mathbb{E}_R(\frac{ALG}{OPT})$ is not used instead.

The first definition allows an algorithm that does abysmally bad on almost all instances, but gets an extremely high value on un probable events. The second normalizes the approximation ratio across all realizations and is more "robust". Does the second metric have a name in the literature?

Improve this question
$\endgroup$
3
  • $\begingroup$ @mathworker21 $ALG \leq OPT$ in maximization problems, so your example wouldn't apply. $\endgroup$
    – user3508551
    Feb 24 at 0:17
  • 1
    $\begingroup$ (i) The post is about average-case analyses? These seem pretty rare in competitive analysis. Could you give some examples? (ii) Note that in the more common case of worst-case competitive analysis of randomized algorithms, it essentially makes no difference as OPT is fixed for a given input. (iii) You seem to have in mind maximization problems, in which case ALG $\le$ OPT in all cases, so ALG can't take a value that is "extremely high" relative to $\alpha$ OPT unless $\alpha \ll 1$. $\endgroup$
    – Neal Young
    Feb 24 at 20:13
  • $\begingroup$ @NealYoung i) One example I can think of is in the prophet secretary problem. The expectation is taken across all possible realisations. ii) I see. iii) I see this, I'm just saying that an $\alpha$-competitive ratio on one metric wouldn't be exactly $\alpha$ competitive on the other metric, and vice versa. I wouldn't be surprised if they're even within a constant ratio, still I see the later as a bit more robust. $\endgroup$
    – user3508551
    Feb 26 at 6:35

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.

Browse other questions tagged or ask your own question.