Online bin packing of fragile objects with application in cellular networks

We study a specific bin packing problem which arises from the channel assignment problems in cellular networks. In cellular communications, frequency channels are some limited resource which may need to share by various users. However, in order to avoid signal interference among users, a user needs to specify to share the channel with at most how many other users, depending on the user’s application. Under this setting, the problem of minimizing the total channels used to support all users can be modeled as a specific bin packing problem as follows: Given a set of items, each with two attributes, weight and fragility. We need to pack the items into bins such that, for each bin, the sum of weight in the bin must be at most the smallest fragility of all the items packed into the bin. The goal is to minimize the total number of bins (i.e., the channels in the cellular network) used. We consider the on-line version of this problem, where items arrive one by one. The next item arrives only after the current item has been packed, and the decision cannot be changed. We show that the asymptotic competitive ratio is at least 2. We also consider the case where the ratio of maximum fragility and minimum fragility is bounded by a constant. In this case, we present a class of online algorithms with asymptotic competitive ratio at most of 1/4+3r/2, for any r>1. A preliminary version of this paper appeared in Proc. of Workshop on Internet and Network Economics (WINE’05, pp. 564–573). The research of W.-T.C. was supported in part by Hong Kong RGC grant HKU5172/03E. The research of F.Y.-L.C. was supported in part by Hong Kong RGC Grant HKU7142/03E. The research of D.Y. was supported by NSFC (10601048). The research of G.Z. was supported in part by NSFC (60573020).