2013 | OriginalPaper | Buchkapitel
New Online Algorithms for Story Scheduling in Web Advertising
verfasst von : Susanne Albers, Achim Passen
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study
storyboarding
where advertisers wish to present sequences of ads (stories) uninterruptedly on a major ad position of a web page. These jobs/stories arrive online and are triggered by the browsing history of a user who at any time continues surfing with probability
β
. The goal of an ad server is to construct a schedule maximizing the expected reward. The problem was introduced by Dasgupta, Ghosh, Nazerzadeh and Raghavan (SODA’09) who presented a 7-competitive online algorithm. They also showed that no deterministic online strategy can achieve a competitiveness smaller than 2, for general
β
.
We present improved algorithms for storyboarding. First we give a simple online strategy that achieves a competitive ratio of 4/(2 −
β
), which is upper bounded by 4 for any
β
. The algorithm is also 1/(1 −
β
)-competitive, which gives better bounds for small
β
. As the main result of this paper we devise a refined algorithm that attains a competitive ratio of
c
= 1 +
φ
, where
$\phi=(1+\sqrt{5})/2$
is the Golden Ratio. This performance guarantee of
c
≈ 2.618 is close to the lower bound of 2. Additionally, we study for the first time a problem extension where stories may be presented simultaneously on several ad positions of a web page. For this parallel setting we provide an algorithm whose competitive ratio is upper bounded by
$1/(3-2\sqrt{2})\approx 5.828$
, for any
β
. All our algorithms work in phases and have to make scheduling decisions only every once in a while.