# Competitive Analysis of Algorithms for an Online Distribution Problem
## 4 Online Algorithms with a Given Threshold Price
Therefore, since \(\bar{p}_{3}^{*}\) is non-negative, then \(\bar{p}_{3}^{*}=\sqrt{p(P+hH)}\). Note that if \(\sqrt{p(P+hH)}<p\) or if \(\sqrt{p(P+hH)}>P\), then \(\bar{p}_{3}^{*}=P\) is the optimal threshold, implying that \(P_{0}\) is accepted at time 0. In fact, in the second case, the competitive ratio is a decreasing function in \(\bar{p}\) in the interval \([p,P]\), while in the first case, the competitive ratio is an increasing function in \(\bar{p}\). However, setting \(\bar{p}_{3}^{*}=p\) implies accepting price \(P_{H}\) at time period \(H\) in the worst case. This is dominated by accepting \(P_{0}\) at time period 0. **Theorem 8**. : _If \(p\leq\sqrt{p(P+hH)}\leq P\), then \(\frac{ALG_{3}^{p_{3}^{*}}}{OPT}\leq\sqrt{\frac{P+hH}{p}}\). Otherwise, \(\frac{ALG_{3}^{p_{3}^{*}}}{OPT}\leq\frac{p}{p}\)._  
Consider now the case in which the minimum price offered from 0 to \(H\) is accepted at time period \(H\) if every prior price has been rejected (algorithm \(\text{ALG}_{4}^{\bar{p}}\)). Although these algorithms are not fairly comparable to the previous one, since the price offered in a period does not expire at the end of the period, the result can serve, in most cases, as an aspirational benchmark. Each of these algorithms can be described as follows. **Algorithm \(\text{ALG}_{4}^{\bar{p}}\):**_Accept the first price that is no greater than \(\bar{p}\). At time period \(H\), accept the minimum price offered from 0 to \(H\) if every prior price has been rejected._  
Let us denote the total cost generated by applying Algorithm \(\text{ALG}_{4}^{\bar{p}}\) by \(ALG_{4}^{\bar{p}}\). **Theorem 9**. : \(\frac{ALG_{4}^{\bar{p}}}{OPT}\leq\max\{\frac{\bar{p}}{p},\frac{\bar{p}+hH}{p}\}\)_._  
Proof of Theorem 9.: Consider first the case in which there exists a time period \(s\) between 0 and \(H-1\) such that \(P_{s}\leq p\). The cost \(ALG_{4}^{\bar{p}}\) generated by algorithm \(\text{ALG}_{4}^{\bar{p}}\) is \(P_{s}+hs\). The optimal offline cost \(OPT\) is no lower than the minimum between \(\bar{p}\) and \(p+hs\). Therefore, \(\frac{ALG_{4}^{\bar{p}}}{OPT}\leq\max\{\frac{P_{s}+hs}{p},\frac{P_{s}+hs}{p+hs }\}\leq\max\{\frac{\bar{p}+hH}{p},\frac{\bar{p}+hs}{p+hs}\}\leq\max\{\frac{ \bar{p}+hH}{p},\frac{\bar{p}}{p}\}\). Consider now the case in which at time period \(H\) the producer accepts the minimum price \(P^{*}\) offered between 0 and \(H\). The cost generated by algorithm \(\text{ALG}_{4}^{\bar{p}}\) is \(P^{*}+hH\), while the optimal offline cost \(OPT\) is no lower than \(P^{*}\), as \(P_{t}\) was greater than \(P^{*}\) for each \(0\leq t<H\). Therefore, in this case, \(\frac{ALG_{4}^{\bar{p}}}{OPT}\leq\frac{P^{*}+hH}{p^{*}}<\frac{\bar{p}+hH}{p}\), since \(P^{*}>\bar{p}\) and \(\frac{P^{*}+hH}{p^{*}}\) are decreasing functions in \(P^{*}\). Therefore, \(\frac{ALG_{4}^{\bar{p}}}{OPT}\leq\max\{\frac{\bar{p}}{p},\frac{\bar{p}+hH}{p}\}\). We now show that this algorithm cannot have a better competitive ratio. Consider first the following instance: \(P_{t}=P\) for all \(0\leq t<s\), \(P_{s}=\bar{p}\), \(P_{t}=p\) for all \(t>s\) and \(h\) such that \(\bar{p}>p+h(s+1)\), i.e., \(h<\frac{\bar{p}-p}{s+1}\). The cost generated by algorithm \(\text{ALG}_{4}^{\bar{p}}\) is \(ALG_{4}^{\bar{p}}=\bar{p}+hs\), while the optimal offline cost is \(OPT=p+h(s+1)\). Therefore, in this instance, \(\frac{ALG_{4}^{\bar{p}}}{OPT}=\frac{\bar{p}+hs}{p+h(s+1)}\rightarrow\frac{ \bar{p}}{p}\) for \(h\to 0\). Consider now the following instance: \(P_{t}=\bar{p}+\epsilon\), where \(\epsilon<<1\), for all \(0\leq t<H-1\) and \(P_{H}=P\). The cost generated by algorithm \(\text{ALG}_{4}^{\bar{p}}\) is \(ALG_{4}^{\bar{p}}=\bar{p}+\epsilon+hH\), while the optimal offline cost is obtained by accepting \(\bar{p}+\epsilon\) at time 0, that is, \(OPT=\bar{p}+\epsilon\). Therefore, in this instance, \(\frac{ALG_{4}^{\bar{p}}}{OPT}=\frac{\bar{p}+\epsilon+hH}{p+\epsilon} \rightarrow\frac{\bar{p}+hH}{p}\) for \(\epsilon\to 0\).