WAOA 2018 Paper Abstract

TITLE: Call Admission Problems on Grids with Advice
AUTHORS: Hans-Joachim Böckenhauer, Dennis Komm and Raphael Wegner

Abstract:
We analyze the call admission problem on grids, thus generalizing previous results for the path graph, where a central authority receives requests that two of the computers in a given network arranged as a grid structure want to communicate. The central authority can then, for every request, either grant it by establishing one of the possible connections in the grid, or reject the request. Thereby, the requests have to be answered in an online fashion, every connection is permanent, and connections have to be edge-disjoint. The goal is to admit as many requests as possible. We are particularly interested to examine how much information about the future requests the central authority needs in order to compute an optimal solution or a solution of some given quality compared to the optimal solution; we quantify this information by studying the advice complexity of the problem. 

Our results show that, without additional information, the central authority cannot perform satisfactorily well, and we establish a lower bound linear in |E| for the number of advice bits needed for near-optimal solutions, where |E| denotes the number of edges in the grid. Furthermore, concerning optimality, we are able to prove nearly tight bounds of at least 0.94|E| and at most 3|E| advice bits. In addition, we state another upper bound in the number of requests k and the number of vertices |V | in the grid of log_2 (5)*k + log_2(3)*|V| + 2 log_2(k) advice bits, which is stronger for a small number of requests.