- Revenue Maximization from Personal TV Advertisements:
In the personal advertisement domain, we focus on the problem of personal advertisements allocation with the objective of revenue maximization. Personalization is the next-generation in the world of advertisement, and while its massive use has been already apparent in the Internet medium, it has not yet been used in the TV medium as there are still challenges to overcome, such as the revenue maximization. Hence, we consider the problem for the TV medium, including its special constraints and the dynamic environment involved.
We propose heuristic algorithms for solving the problem which outperforms the state-of-the-art Integer Programming solver (IBM ILOG CPLEX). In addition, we provide a theoretical analysis of the problem, and provide polynomial time approximation schemes (PTASs) to solve restricted instances. Since the problem is a generalization of the well-known Multiple Knapsack Problem, our results are generic and can be applied to other domains as well.