# Competitive Analysis of Algorithms for an Online Distribution Problem
## 4 Online Algorithms with a Given Threshold Price  
In this section, we analyze the class of algorithms in which the first price less than or equal to a given threshold \(\bar{p}\) (\(p\leq\bar{p}\leq P\)) is accepted. This type of online algorithm is very useful from a practical point of view, given that it is simple to use. Moreover, we will now prove that it has a better worst-case performance with respect to the algorithms with a given time of acceptance. We first consider the case in which, at time period \(H\), the price \(P_{H}\) is accepted if every prior price has been rejected (algorithm \(\mathrm{ALG}_{3}^{\bar{p}}\)); then, we consider 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 (algorithms \(\mathrm{ALG}_{4}^{\bar{p}}\)). Each of the algorithms \(\mathrm{ALG}_{3}^{\bar{p}}\) can be formally described as follows. **Algorithm \(\mathrm{ALG}_{3}^{\bar{p}}\):**_Accept the first price that is no greater than \(\bar{p}\). At time period \(H\), accept \(P_{H}\) if every prior price has been rejected._  
If we denote the total cost obtained by applying the algorithm \(\mathrm{ALG}_{3}^{\bar{p}}\) by \(\mathrm{ALG}_{3}^{\bar{p}}\), then the following theorem holds. Theorem 4.2: \(\frac{ALG_{3}^{\bar{p}}}{OPT}\leq\max\{\frac{\bar{p}}{p},\frac{P+hH}{\bar{p}}\}\)_._  
Proof of Theorem 4.2.: Consider first the case in which there exists a time period \(s\) between \(0\) and \(H-1\) such that \(P_{s}\leq\bar{p}\). The cost \(\mathrm{ALG}_{3}^{\bar{p}}\) generated by algorithm \(\mathrm{ALG}_{3}^{\bar{p}}\) is \(P_{s}+hs\). The optimal offline cost \(OPT\) is no lower than the minimum between \(\bar{p}\) and \(\bar{p}+hs\), as \(P_{t}\) is greater than \(\bar{p}\) for \(t<s\) and it is greater or equal than \(p\) starting from time period \(s\). Therefore, \(\frac{ALG_{3}^{\bar{p}}}{OPT}\leq\max\{\frac{P_{s}+hs}{\bar{p}},\frac{P_{s}+hs }{p+hs}\}\leq\max\{\frac{P+hH}{\bar{p}},\frac{P+hs}{p+hs}\}\leq\max\{\frac{P+ hH}{\bar{p}},\frac{P}{p}\}\). Consider now the case in which the producer accepts \(P_{H}\). The cost generated by the algorithm \(\mathrm{ALG}_{3}^{\bar{p}}\) is no greater than \(P+hH\), while the optimal cost \(OPT\) is no lower than \(\bar{p}\), as \(P_{t}\) was greater than \(\bar{p}\) for each \(0\leq t<H\). Therefore, in this case, \(\frac{ALG_{3}^{\bar{p}}}{OPT}\leq\frac{P+hH}{\bar{p}}\). Hence, \(\frac{ALG_{3}^{\bar{p}}}{OPT}\leq\max\{\frac{\bar{p}}{p},\frac{P+hH}{\bar{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}+hs>p+h(s+1)\), i.e., \(h<\bar{p}-p\), and \(h<\frac{P-p}{s+1}\). The cost generated by algorithm \(\mathrm{ALG}_{3}^{\bar{p}}\) is \(\bar{p}+hs\), while the optimal offline cost is \(OPT=p+h(s+1)\). Therefore, in this instance, \(\frac{ALG_{3}^{\bar{p}}}{OPT}=\frac{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 \(\mathrm{ALG}_{3}^{\bar{p}}\) is \(P+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_{3}^{\bar{p}}}{OPT}=\frac{P+hH}{\bar{p}+\epsilon}\rightarrow\frac{P+ hH}{\bar{p}}\) for \(\epsilon\to 0\). Let us now compute the optimal threshold \(\bar{p}_{3}^{\bar{p}}\) in the worst case. **Theorem 7**. : _In the worst case, if \(p\leq\sqrt{p(P+hH)}\leq P\), then the optimal threshold is \(\bar{p}_{3}^{*}=\sqrt{p(P+hH)}\)._  
Proof of Theorem 7.: Consider the competitive ratio \(\max\{\frac{p}{p},\frac{P+hH}{p}\}\). Since the first component is increasing in \(\bar{p}\) and the second is decreasing in \(\bar{p}\), the threshold that minimizes the competitive ratio satisfies \(\frac{p}{p}=\frac{P+hH}{p}\).