| Popis: |
A well-studied problem in the online setting, where requests have to be answered immediately without knowledge of future requests, is the call admission problem. In this problem, we are given nodes in a communication network that request connections to other nodes in the network. A central authority may accept or reject such a request right away, and once a connection is established its duration is unbounded and its edges are blocked for other connections. This paper examines the admission problem in tree networks. The focus is on the quality of solutions achievable in an advice setting, that is, when the central authority has some information about the incoming requests. We show that \(O(m \log d)\) bits of additional information are sufficient for an online algorithm run by the central authority to perform as well as an optimal offline algorithm, where m is the number of edges and d is the largest degree in the tree. In the case of a star tree network, we show that \(\varOmega (m \log d)\) bits are also necessary (note that \(d=m\)). Additionally, we present a lower bound on the advice complexity for small constant competitive ratios and an algorithm whose competitive ratio gradually improves with added advice bits to \(2 \lceil \log _{2} n \rceil \), where n is the number of nodes. |
