# Competitive Analysis of Algorithms for an Online Distribution Problem
## 6 Computational Results
### Randomly Generated Instances
Moreover, the maximum ratios tend to be very close to the competitive ratios shown in Table 1. \(\text{ALG}_{1}^{0}\) is significantly dominated by \(\text{ALG}_{3}^{P_{5}^{4}}\), which is dominated by \(\text{ALG}_{4}^{P_{5}^{4}}\) when the maximum ratios are computed, and tends to be dominated on average. The performance of the latter algorithm is very good. For each probability distribution, the average and maximum ratios decrease, even if not monotonically, with \(h\) and they are equal to 1, as expected, for \(h=100\) (see Theorem 3). The ratios are very different with different probability distributions. In particular, the uniform distribution gives the largest ratios, while the normal distribution with a mean of 150 and a standard deviation of 5 gives the smallest ratios. We do not show in detail the performance of the algorithms \(\text{ALG}_{1}^{j}\) and \(\text{ALG}_{2}^{j}\) for \(j>0\). As expected, the computational results show that the average and the maximum ratios increase with \(j\) and that \(\text{ALG}_{2}^{j}\) dominates \(\text{ALG}_{1}^{j}\) (as an example, see Table 10 for the case with \(H=5\) and Uniform distribution). Finally, the results show that, for any probability distribution, the algorithm \(\text{ALG}_{5}^{k}\) used to optimally solve the Secretary problem is significantly worse than the algorithms we propose to solve the distribution problem, both for \(H=5\) and \(H=15\). Moreover, the average and maximum ratios of the algorithm \(\text{ALG}_{5}^{k}\) tend to increase when \(k\) increases due to the penalty cost. These results highlight the need for designing specific algorithms for \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & \(\text{ALG}_{1}^{0}\) & \(\text{ALG}_{1}^{1}\) & \(\text{ALG}_{1}^{2}\) & \(\text{ALG}_{1}^{3}\) & \(\text{ALG}_{1}^{4}\) & \(\text{ALG}_{1}^{5}\) \\ \hline Average & 1.2187 & 1.3786 & 1.5374 & 1.7047 & 1.85472 & 2.0103 \\ Maximum & 1.7514 & 2.1737 & 2.3897 & 2.6502 & 2.8602 & 3.1111 \\ \hline  & \(\text{ALG}_{2}^{0}\) & \(\text{ALG}_{1}^{1}\) & \(\text{ALG}_{2}^{2}\) & \(\text{ALG}_{2}^{3}\) & \(\text{ALG}_{2}^{4}\) & \(\text{ALG}_{2}^{5}\) \\ \hline Average & 1.2187 & 1.2345 & 1.3232 & 1.4440 & 1.5721 & 1.7065 \\ Maximum & 1.7514 & 1.8865 & 1.9202 & 2.1267 & 2.1902 & 2.1111 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Average and maximum ratios for \(\text{ALG}_{1}^{j}\) and \(\text{ALG}_{2}^{j}\) when \(H=5\) and a uniform distribution is assumed. \begin{table}
\begin{tabular}{c c c c c c c c c c c} \hline \hline  & & \multicolumn{4}{c}{**Uniform**} & \multicolumn{4}{c}{**Exponential**} \\ \(h\) & \(\text{ALG}_{1}^{0}\) & \(\text{ALG}_{3}^{P_{5}^{4}}\) & \(\text{ALG}_{4}^{P_{4}^{4}}\) & \(\text{ALG}_{3}^{1}\) & \(\text{ALG}_{5}^{3}\) & \(\text{ALG}_{1}^{0}\) & \(\text{ALG}_{3}^{P_{5}^{4}}\) & \(\text{ALG}_{4}^{P_{5}^{4}}\) & \(\text{ALG}_{5}^{1}\) & \(\text{ALG}_{5}^{5}\) \\ \hline
0.01 & 1.9976 & 1.4094 & 1.0015 & 1.9718 & 2.0007 & 1.9996 & 1.4089 & 1.0015 & 2.0015 & 2.0015 \\
0.1 & 1.9801 & 1.4044 & 1.0147 & 1.9851 & 2.0070 & 1.9960 & 1.3990 & 1.0147 & 2.0150 & 2.0150 \\
1 & 1.9417 & 1.4314 & 1.1316 & 2.1188 & 2.1188 & 1.9608 & 1.4314 & 1.1304 & 2.1500 & 2.1500 \\
10 & 1.7522 & 1.6404 & 1.5727 & 3.4554 & 3.4554 & 1.7636 & 1.6636 & 1.6455 & 3.5000 & 3.5000 \\
100 & 1.0000 & 1.0000 & 1.0000 & 16.8800 & 16.8800 & 1.0000 & 1.0000 & 1.0000 & 17.0000 & 17.0000 \\ Av.