The competitiveness of randomized algorithms for on-line Steiner tree and on-line spanning tree problems

[[abstract]]This paper considers a family of randomized on-line algorithms, Algorithm R(m), where 1⩽m⩽n-1 and n is the number of input points, for the on-line Steiner tree and on-line spanning tree problems on Euclidean space. The main result is that if m is a fixed constant, the competitive ratios of Algorithm R(m) for the on-line Steiner tree and spanning tree problems are Θ(n). The authors also show that the competitive ratio of Algorithm R(n-1), which is deterministic greedy algorithm, for the on-line spanning tree problem is the same as that for the on-line Steiner tree problem, which is O(log n)[[fileno]]2030209010077[[department]]資訊工程學