We study a variant of the generalized assignment problem ( gap ), which we label all-or-nothing gap ( agap ). We are given a set of items, partitioned into n groups, and a set of m bins. Each item ℓ has size s ℓ > 0, and utility a ℓ j ⩾ 0 if packed in bin j . Each bin can accommodate at most one item from each group; the total size of the items in a bin cannot exceed its capacity. A group of items is satisfied if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from satisfied groups is maximized. We motivate the study of agap by pointing out a central application in scheduling advertising campaigns. Our main result is an O (1)-approximation algorithm for agap instances arising in practice, in which each group consists of at most m /2 items. Our algorithm uses a novel reduction of agap to maximizing submodular function subject to a matroid constraint. For agap instances with a fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS) , relying on a nontrivial LP relaxation of the problem. We present a (3 + ε)-approximation as well as PTASs for other special cases of agap , where the utility of any item does not depend on the bin in which it is packed. Finally, we derive hardness results for the different variants of agap studied in this paper.

In this paper we consider the problem of allocating personal TV advertisements when the viewers' viewing capacities are uncertain. We focus on the Mobile TV medium as a personal platform taking into account special constraints that are motivated by the TV medium. Since the problem is NP-Hard, we present a sequential solution procedure and propose several heuristic algorithms for solving it. Through computational experiments on different scenarios of uncertainty, the performances of these heuristics were compared to the performance in the deterministic case where the actual viewing capacities are known in advance. The performance of these heuristics was close to that of the deterministic even for scenarios where uncertainty was very high while the CombinedRatingRobust algorithm seems to be the best for most scenarios. In general, the heuristic algorithms that consider uncertainty in advance seem to be preferable over those that only adapt to it after it has been discovered. Though this paper is oriented for Mobile TV, the proposed algorithms are suitable for other personal push-advertisement methods such as SMS (Short Message Service) and MMS (Multimedia Messaging Service).

Personal advertisements are the next-generation in the world of advertisement. In this article we consider the personal advertisement allocation problem with constraints that are motivated by the TV and Mobile advertisement worlds. This problem is a version of the Generalized Multi-Assignment Problem, defined as an extension of GAP with assignment restrictions and all-or-nothing constraints. We present an Integer Programming (IP) model of the problem, prove that it is an NP-hard problem, and propose heuristic algorithms to solve it. Through computational experiments, we compare the performance of these heuristics to solutions obtained with IP solvers. We show that the Backtrack Heuristic outperforms the others and on average it attains 98% of the possible revenue. Though this paper is Mobile TV oriented, the results suit any other personal advertisement "push" method in the mobile market such as SMS (Short Message Service) and MMS (Multimedia Messaging Service).