Space constrained selection problems for data warehouses and pervasive computing

Space constrained optimization problems arise in a multitude of important applications such as data warehouses and pervasive computing. A typical instance of such problems is to select a set of items of interest, subject to a constraint on the total space occupied by these items. Assuming that each item is associated with a benefit, for a suitably defined notion of benefit, one wishes to optimize the total benefit for the selected items. We show that in many important applications, one faces variants of this basic problem in which the individual items are sets themselves, and each set is associated with a benefit value. We present instances of such problems in the context of data warehouse management and pervasive computing, derive their complexity, and propose several techniques for solving them. Since there are no known approximation algorithms for these problems, we explore the use of greedy and randomized techniques. We present a detailed performance study of the algorithms, highlighting the efficiency of the proposed solutions and the benefits of each approach. Finally, we present a worst-case analysis of the algorithms, which can be useful in practice for choosing among the alternatives. The solutions proposed in the paper are generic and likely to find applications in many more problems of interest than those mentioned above.