Article ID: | iaor20103516 |
Volume: | 57 |
Issue: | 3 |
Start Page Number: | 517 |
End Page Number: | 537 |
Publication Date: | Jul 2010 |
Journal: | Algorithmica |
Authors: | Azar Yossi, Feige Uriel, Glasner Daniel |
We consider the on-line version of the maximum vertex disjoint path problem when the underlying network is a tree. In this problem, a sequence of requests arrives in an on-line fashion, where every request is a path in the tree. The on-line algorithm may accept a request only if it does not share a vertex with a previously accepted request. The goal is to maximize the number of accepted requests. It is known that no on-line algorithm can have a competitive ratio better than Ω(log