Maximizing revenue with allocation of multiple advertisements on a Web banner
Introduction
With the continuing growth of Web usage, Web advertising becomes a more dominant form of marketing every year. According to the Interactive Advertising Bureau, Web advertising revenues for 2008 totaled $23.4 billion in the U.S. only [1]. A special form of Web advertising is pixel advertisement, the presentation of several small advertisements on a larger, two-dimensional space. It originated in 2005 from the English student Alex Tew's “Million Dollar Homepage” [2]. In order to make some money, he came up with the idea to sell advertising space in a unique concept. The homepage displays a 1000 by 1000 pixel grid from which blocks of 10 by 10 pixels could be bought for 1 dollar per pixel. Buyers could place an advertisement image on their pixels and let it link to their website. The pixel advertisement website became a great success, due to its novel proposition [3]. The copycats that arose could not repeat the success of the “Million Dollar Homepage”, but applying the concept in a different way may still be interesting. In this work, we apply the pixel advertisement concept to Web banners. Representing 22 percent of the total Web advertisement revenue in 2008, banner advertisements remain a significant source of income for Web advertisers [1]. A sample from the “Million Dollar Homepage” in the shape of a banner is given in Fig. 1.
In our modified version of the concept, advertisers commit small Web advertisements, without specifying a location on the banner where the advertisement should be placed. In the original approach, advertisers choose their own pixels from the ones available and are sure of placement, while here not every advertisement is placed on the banner. Each advertisement has a certain price per pixel, which can be obtained either by negotiations with the space-owner or just represent the value the advertiser is asked to pay for it. If an advertisement is placed, the advertiser has to pay the costs corresponding to the size of the advertisement. An assumption we make is that we have more advertisements than would fit on the banner, so some advertisements of the set may not be placed. This increases the competition among advertisers which will lead to higher prices per pixel. On the other hand, smaller advertisements are more affordable, which makes Internet advertising more accessible for anyone. When we have a set of advertisements, we allocate them across the banner in such a way that the revenue of the space-owner is maximized. We name this modified version of the pixel advertisement concept, multiple advertisement allocation.
This research deals specifically with the advertisement allocation process and focuses on finding a suitable pattern generating algorithm. The problem tackled in this work can be seen as a variant of the well-known cutting and packing problems in the literature. When following the typology in [4], our problem can be classified as a two-dimensional, single, orthogonal, knapsack problem. In the knapsack problem, a strongly heterogeneous assortment of small items has to be allocated to a given set of large objects. The availability of the large objects is limited in a way that not all small items can be accommodated. The objective is to maximize the value of the accommodated items. The term single means we have only one large object to place our advertisements in, namely the banner. In orthogonal patterns, the edges of small items are set parallel to the edges of the large object and rotation is not allowed [5]. The problem is NP-hard [6], making it extremely time-consuming to find the optimal solution. Besides this, we also plan to apply our solution on the Web which makes temporal restrictions highly relevant. As a consequence of all these constraints, we decided to apply heuristics to find adequate solutions.
Due to the nature of our problem we chose a simulation-based research methodology. We implement several heuristic algorithms for generating adequate allocation patterns for multiple advertisement placement. In addition, we implement a brute force search algorithm that finds the optimal allocation pattern. In our experiments we run two simulations, a small and a large one. The small simulation benchmarks the heuristics against the brute force search algorithm using a small problem size, in order to emphasize the difficulties of using an optimal solution yielding approach under temporal constraints. The large simulation uses a normal problem size with only heuristic algorithms, to gain a better insight into their performance. We analyse the performance of the different algorithms with respect to their effectiveness and efficiency.
In this paper, we extend our previous work on pixel advertisement [7] by refining the experimental design. We use more realistic sets of advertisements, improved the GRASP algorithm, and added two other algorithms (i.e., the brute force search algorithm, and the greedy stripping algorithm). In addition, we do a more thorough analysis of the effectiveness and efficiency of the algorithms, also covering the influence sorting criteria and banner types have on the results.
The rest of this paper is organized as follows. First, we discuss related work in Section 2. Then, we give the problem formulation and we present a brute force search implementation for finding the optimal solution in Section 3. Four heuristic algorithms that generate adequate solutions are presented in Section 4. The description of the experimental design is given in Section 5. In Section 6 we present and analyse the results of the simulation experiments. Finally, Section 7 concludes the paper and identifies future work directions.
Section snippets
Related work
At the current moment, there is very little literature available on pixel advertisement. In [3], Web advertisement is discussed in general and the “Million Dollar Homepage” is analysed. The author identifies the success factors and also proposes some improvements for the pixel advertisement concept. Such an improvement is a heuristic approach for placing multiple advertisements on a banner in [8]. We formalized this heuristic-based approach and performed an extensive evaluation in [7].
Other
Problem definition and optimal solution
The purpose of this section is to specify the problem that we try to solve, and to discuss the process of finding the optimal solution. First, we give the formal problem definition together with an integer programming formulation in Section 3.1. Second, we elaborate upon the optimal solution and present a brute force search algorithm for finding the optimal solution in Section 3.2.
Four heuristic-based algorithms
In this section we present four heuristic-based algorithms for the multiple advertisement allocation problem. First we give the initialization for our heuristic algorithms. Then, we present the left justified algorithm, the orthogonal algorithm, the GRASP constructive algorithm, and the greedy stripping algorithm.
Experimental design
We run two simulations in which algorithms for multiple advertisement allocation are compared. First, we show that finding the optimal solution is extremely time-consuming by benchmarking the heuristic algorithms against the brute force search algorithm. Second, we run a large simulation for comparing the heuristic algorithms.
In the heuristics simulation, every simulation cycle has a different configuration of its parameters. We distinguish the following three configuration parameters of which
Simulation results
In this section we present and analyse the results of our simulations. First, we present the results of the simulations focused on finding the optimal solution in Section 6.1. These simulations are run on a decreased problem size. Second, we present the results of the heuristic algorithm benchmark in Section 6.2, that uses the experimental design as presented in Section 5.
Conclusions and future work
In this paper, we have presented heuristic-based solutions for a modified version of the pixel advertisement problem. We focused on allocating multiple advertisements on a banner and proposed several heuristic algorithms that provide adequate solutions for the problem. Our experiments give insight into the effectiveness and efficiency of these algorithms. The orthogonal algorithm is the most effective, followed by the left justified algorithm. In contrast, the greedy stripping algorithm is the
References (36)
- et al.
An improved typology of cutting and packing problems
European Journal of Operational Research
(2007) - et al.
An exact algorithm for general, orthogonal, two-dimensional knapsack problems
European Journal of Operational Research
(1995) - et al.
Scheduling advertisements on a Web page to maximize revenue
European Journal of Operational Research
(2006) - et al.
On the two-dimensional knapsack problem
Operations Research Letters
(2004) - et al.
A new exact method for the two-dimensional orthogonal packing problem
European Journal of Operational Research
(2007) A sequential heuristic procedure for the two-dimensional cutting-stock problem
International Journal of Production Economics
(2006)- et al.
Heuristic approaches for the two- and three-dimensional knapsack packing problem
Computers & Operations Research
(2009) - et al.
An approximation algorithm for solving unconstrained two-dimensional knapsack problems
European Journal of Operational Research
(1995) - et al.
Two-dimensional packing problems: a survey
European Journal of Operational Research
(2002) A population heuristic for constrained two-dimensional non-guillotine cutting
European Journal of Operational Research
(2004)