# Competitive Analysis of Algorithms for an Online Distribution Problem
## 3 Online Algorithms with a Given Time of Acceptance  
In this section, we provide the competitive ratio of online algorithms in which the minimum price \(P_{j}\) offered at a given time period \(j\) is accepted. Each of these algorithms can be formally described as follows. **Algorithm \(\text{ALG}^{j}_{1}\)**:**_At time period \(j\), accept \(P_{j}\)._  
If we denote the total cost obtained by applying the algorithm \(\text{ALG}^{j}_{1}\) by \(ALG^{j}_{1}\) and the optimal cost of the offline problem by \(OPT\), then the following theorem holds. Theorem 3.1: \(\frac{ALG^{j}_{1}}{OPT}\leq\frac{P+hj}{p}\)_._  
Proof of Theorem 3.1: Since the producer accepts price \(P_{j}\) at time period \(j\), the total cost obtained by applying algorithm \(A^{j}_{1}\) is \(ALG^{j}_{1}=P_{j}+hj\). The optimal offline cost \(OPT\) is not lower than \(p\). Therefore, \(\frac{ALG^{j}_{1}}{OPT}\leq\frac{P_{j}+hj}{p}\leq\frac{P+hj}{p}\). We now show that this algorithm cannot have a better competitive ratio. Consider first the following instance: \(j>0\), \(P_{j}=P\), \(P_{t}=p\) for \(t\
eq j\). The total cost generated by the algorithm \(\text{ALG}^{j}_{1}\) is \(P+hj\), while the optimal offline cost is \(OPT=p\) (obtained by accepting the price offered at time \(0\)); therefore, in this instance, \(\frac{ALG^{j}_{1}}{OPT}=\frac{P+hj}{p}\). Consider now the following instance: \(j=0\), \(P_{0}=P\), \(P_{t}=p\) for \(0<t\leq H\) and \(h<P-p\). Since the total cost generated by the algorithm is \(ALG^{j}_{1}=P\) and the optimal cost is \(OPT=p+h\) (obtained by accepting the price offered at time \(1\)), then in this instance, \(\frac{ALG^{j}_{1}}{OPT}=\frac{P}{p+h}\rightarrow\frac{P}{p}\) for \(h\to 0\). Since the worst-case ratio of the algorithms \(\text{ALG}^{j}_{1}\) is increasing in \(j\), the following theorem holds. Theorem 3.2: _In the worst case, the best algorithm with a given time of acceptance is \(ALG^{0}_{1}\), with a competitive ratio \(\frac{p}{p}\)._This result is very interesting also from a managerial point of view. If \(\text{ALG}_{1}^{0}\) is used, the maximum percent cost increase with respect to the optimal solution of the offline problem is given by \((\frac{P}{p}-1)*100\). For example, if \(\frac{P}{p}=2\), this means that the online algorithm will give a percent cost increase of at most 100% with respect to the cost of the optimal solution of the offline problem. We now show that there exists a class of instances in which the algorithm \(\text{ALG}_{1}^{0}\) gives an optimal solution to the online problem. In particular, when the penalty cost \(h\) is greater than or equal to the difference between the default price \(P\) and the minimum price \(p\), it is always optimal to select the first offered price. Theorem 3.1: \(ALG_{1}^{0}\) _is optimal in the class of instances with \(h\geq P-p\)._  
Proof of Theorem 3.1: The total cost \(ALG\) generated by any algorithm ALG either is the cost of accepting \(P_{0}\) at time 0, that is, \(ALG_{1}^{0}\), or is not lower than the cost of accepting the minimum price \(p\) at time 1, that is, \(p+h\). Since in the latter case, \(ALG\geq p+h\geq P\geq ALG_{1}^{0}\), as \(h\geq P-p\) and \(ALG_{1}^{0}\leq P\), then \(\text{ALG}_{1}^{0}\) gives an optimal solution. We now analyze the worst-case performance of online algorithms in which the minimum price offered from 0 to a given time period \(j\) is accepted at time period \(j\). Although these algorithms are not fairly comparable to the previous ones, since the price offered in a period does not expire at the end of the period, the results can serve, in most cases, as an aspirational benchmark. Each of these algorithms can formally be described as follows. **Algorithm \(\text{ALG}_{2}^{j}\)**: _At time period \(j\), accept the minimum price offered from time period 0 to time period \(j\)._  
If we denote the total cost obtained by applying the algorithm \(\text{ALG}_{2}^{j}\) by \(ALG_{2}^{j}\), then the following theorem holds.