<p>It seems like the consensus is to define an <span class="math-container">$\alpha$</span>-competitive algorithm if <span class="math-container">$\mathbb{E}_R(ALG) \geq \alpha \mathbb{E}_R(OPT)$</span> where <span class="math-container">$\mathbb{E}_R$</span> is the expected value taken across the problem instances.</p>
<p>I am wondering why the more natural definition of <span class="math-container">$\mathbb{E}_R(\frac{ALG}{OPT})$</span> is not used instead.</p>
<p>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 &quot;robust&quot;. Does the second metric have a name in the literature?</p>

CC BY-SA 4.0
2023-02-24T00:17:45.547Z
@mathworker21 $ALG \leq OPT$ in maximization problems, so your example wouldn't apply.
user3508551
CC BY-SA 4.0
2023-02-24T20:13:17.867Z
(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$.
Neal Young
CC BY-SA 4.0
2023-02-26T06:35:03.680Z
@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.
user3508551
<approximation-algorithms>
Why is the competitive ratio defined as $\mathbb{E}(ALG)/\mathbb{E}(OPT)$ vs $\mathbb{E}(ALG/OPT)$?
user3508551
# Why is the competitive ratio defined as $\mathbb{E}(ALG)/\mathbb{E}(OPT)$ vs $\mathbb{E}(ALG/OPT)$?

(Asked by: username_0 on 2023-02-22)

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?

**Tags:** approximation-algorithms

> **Comments:**
> **username_0**: @mathworker21 $ALG \leq OPT$ in maximization problems, so your example wouldn't apply.  
> **username_1**: (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$.  
> **username_0**: @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.  

---

## 0 answers

