| Abstract: |
Call admission control is the problem of deciding for a given set of connection requests which of them to accept and which to reject, with the goal of maximizing the profit obtained from the
accepted requests. The problem is considered in a scenario with advance reservations where users can specify several alternatives for when and how they want their connections to be established.
Two variants are studied: In BCA (batch call admission), all calls request to be established at the same time. In GCA (general call admission), every request specifies a starting time and
duration. Both variants generalize the well-studied unsplittable flow problem. For star networks, approximation algorithms with constant ratio for BCA with arbitrary edge capacities and for GCA
with unit edge capacities are presented. For GCA with arbitrary edge capacities, ratio O(log R) is achieved, where R is the ratio of the maximum to the minimum edge capacity. For trees and trees
of rings with unit edge capacities, constant-factor approximation algorithms for BCA are given. |
