Call admission problems on trees
Hans-Joachim Böckenhauer, Nina Corvelo Benz, Dennis Komm · Theoretical Computer Science · 2022
We are given nodes in a communication network that request connections to other nodes. 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 cannot be used for other connections; actions are performed without knowledge of future requests, that is, we consider an online setting. We examine this so-called call 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 a certain amount of information on the incoming requests. We show that O(mlog2d) 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 network. In the case of a star tree network, we show that Ω(mlog2d) bits are also necessary (note that d=m). We also 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⌈log2n⌉, where n is the number of nodes in the network.