Revenue maximization for multiple advertisements placement on a web banner using a pixel-price model

The aim of this paper is to optimize the allocation of multiple advertisements on a Web banner, where the price of an advertisement depends on the location at the banner. This problem can be defined as a two-dimensional single orthogonal knapsack problem with a location-based pixel-price model. A formulation is proposed in which the problem is specified as a 0–1 integer programming problem. As this problem is NP-complete, we mainly focus on a heuristic approach to solve the problem. We propose two new heuristic algorithms: the reactive GRASP algorithm and the partitioning left-justified algorithm. Next to that, we present an exact algorithm that is able to solve small problem instances in a reasonable time. These newly presented algorithms are compared with respect to efficiency and effectiveness to existing algorithms that solve the problem without a location-based pixel-price model. To test the quality of the algorithms, we have executed two experiments. The results of these experiments show that overall the reactive GRASP algorithm is the most effective algorithm, whereas the greedy stripping algorithm is the most efficient.