Maximizing revenue with allocation of multiple advertisements on a Web banner

https://doi.org/10.1016/j.cor.2011.01.006Get rights and content

Abstract

The problem addressed in this paper is the allocation of multiple advertisements on a Web banner, in order to maximize the revenue of the allocated advertisements. It is essentially a two-dimensional, single, orthogonal, knapsack problem, applied to pixel advertisement. As this problem is known to be NP-hard, and due to the temporal constraints that Web applications need to fulfill, we propose several heuristic algorithms for generating allocation patterns. The heuristic algorithms presented in this paper are the left justified algorithm, the orthogonal algorithm, the GRASP constructive algorithm, and the greedy stripping algorithm. We set out an experimental design using standard banner sizes, and primary and secondary sorting criteria for the set of advertisements. We run two simulations, the first simulation compares the heuristics with an optimal solution found using brute force search, and the second simulation compares the heuristic algorithms to gain a better insight into their performance. Finding a suitable pattern generating algorithm is a trade-off between effectiveness and efficiency. Results indicate that allocating advertisements with the orthogonal algorithm is the most effective. In contrast, allocating advertisements using the greedy stripping algorithm is the most efficient. Furthermore, the best settings per algorithm for each banner size are given.

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)

  • K.K. Lai et al.

    Developing a simulated annealing algorithm for the cutting stock problem

    Computers & Industrial Engineering

    (1997)
  • R. Alvarez-Valdes et al.

    A tabu search algorithm for a two-dimensional non-guillotine cutting problem

    European Journal of Operational Research

    (2007)
  • R.E. Korf

    Depth-first iterative-deepening: an optimal admissible tree search

    Artificial Intelligence

    (1985)
  • Interactive Advertising Bureau. Internet advertising revenue report,...
  • Tew A. Million Dollar Homepage,...
  • A. Wojciechowski

    An improved Web system for pixel advertising

  • M.R. Garey et al.

    Computers and intractability; a guide to the theory of NP-completeness

    (1990)
  • A. Knoops et al.

    Single pattern generating heuristics for pixel advertisements

  • Cited by (0)

    View full text