Maximizing Revenue with Allocation of Multiple Advertisements on a Web Banner

V Boskamp, A Knoops, Flavius Frasincar, AF Gabor

Research output: Contribution to journalArticleAcademicpeer-review

14 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)1412-1424
Number of pages13
JournalComputers and Operations Research
Issue number10
Publication statusPublished - 2011

Research programs

  • EUR ESE 32


Dive into the research topics of 'Maximizing Revenue with Allocation of Multiple Advertisements on a Web Banner'. Together they form a unique fingerprint.

Cite this