Online knapsack of unknown capacity: How to optimize energy consumption in smartphones

We propose a new variant Of the standard online knapsack problem where the only information missing to the provided instances is the capacity B of the knapsack. We refer to this problem as the online Knapsack of Unknown Capacity (KUC) problem. Any algorithm solving the KUC problem must provide a strategy for filling online the knapsack until its capacity is revealed. When the knapsack capacity is revealed, no other item can be inserted and also the last inserted item is discarded if it does not completely fit in the knapsack. Apart for the interest in a new version of the fundamental knapsack problem, the motivations that lead to define this new variant come from energy consumption constraints in smartphones communications. We provide lower and upper bounds to the problem for various cases. In general, we design an optimal algorithm admitting a :1/2-competitive ratio. When all items admit uniform ratio of profit over size, our algorithm provides a 49/86 = .569 ... competitive ratio that leaves some gap with the provided bound of 1/phi =.618 ..., the inverse of the golden number. We then conduct experimental analysis for the competitive ratio guaranteed algorithms compared to the optimum and to various heuristics.