Online Bottleneck Matching on a Star

In this study, we focus on the problem of online bottleneck matching on a star graph. Given m servers fixed on m leaf nodes on the star graph, m requests arrive one by one in an online fashion. Upon the arrival of each request, the algorithm must immediately match it to an unmatched server with the objective of minimizing the maximum matching distance. For the star, the ratio of the length of the longest edge to the length of the shortest edge is \(\alpha \) . When \(m\ge 3\) , we establish a competitive ratio lower bound of \(\frac{\sqrt{2\alpha ^2+2}+2\alpha }{\alpha +1}\) and prove that the competitive ratio of the permutation algorithm is \(\frac{4\alpha }{\alpha +1}\) , this ratio is tight. Additionally, we design an optimal online algorithm with a competitive ratio of \(\frac{3\alpha +1}{\alpha +1}\) for the case in which the star graph has only two types of edges. When \(m=2\) , we prove that the greedy algorithm achieves an optimal competitive ratio of 2.