Online Bottleneck Matching on a Ring
摘要
On a ring, given m servers and m requests arriving one by one in an online fashion. Upon each request arrival, it needs to be immediately matched to a server, generating a matching distance on the ring. The objective is to find a matching where each server and each request are strictly matched once, minimizing the maximum matching distance. When the m servers are evenly distributed on the ring, we prove that the classical greedy algorithm achieves an optimal competitive ratio of m. When \(m=3\) , using polar coordinates to partition the ring into three intervals, we provide optimal online algorithms for four parameter scenarios where the competitive ratio depends on the server spacing ratio.