Bin-packing with fragile objects and frequency allocation in cellular networks

N. Bansal, Z. Liu, A. Sankar

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    11 Citaten (Scopus)
    1 Downloads (Pure)


    We consider two related optimization problems: bin-packing with fragile objects and frequency allocation in cellular networks. The former is a generalization of the classical bin-packing problem and is motivated by the latter. The problem is as follows: each object has two attributes, weight and fragility. The goal is to pack objects into bins such that, for every bin, the sum of weights of objects in that bin is no more than the fragility of any object in that bin. We consider approximation algorithms for this problem. We provide a 2-approximation to the problem of minimizing the number of bins. We also show a lower bound of 3/2 on the approximation ratio. Unlike for the classical bin-packing problem, this lower bound holds in the asymptotic case. We then consider the approximation with respect to fragility and provide a 2-approximation algorithm (i.e., our algorithm uses the same number of bins as the optimum, but the weight of objects in a bin can exceed the fragility by a factor of 2). We then consider the frequency allocation problem (which is a special case of bin-packing with fragile objects) and give improved approximation algorithms for it. Finally, we consider a probabilistic setting and show that our algorithm for frequency allocation approaches optimality as the number of users increases.
    Originele taal-2Engels
    Pagina's (van-tot)821-830
    TijdschriftWireless Networks
    Nummer van het tijdschrift6
    StatusGepubliceerd - 2009


    Duik in de onderzoeksthema's van 'Bin-packing with fragile objects and frequency allocation in cellular networks'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit