New Online Algorithms for Story Scheduling in Web Advertising

Susanne Albers, Achim Passen

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

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 ϕ=(1+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-22)≈5.828, for any β. All our algorithms work in phases and have to make scheduling decisions only every once in a while.

Original languageEnglish
Pages (from-to)1-25
Number of pages25
JournalAlgorithmica
Volume81
Issue number1
DOIs
StatePublished - 15 Jan 2019

Keywords

  • Competitive analysis
  • Multiple ad positions
  • One ad position
  • Storyboarding

Fingerprint

Dive into the research topics of 'New Online Algorithms for Story Scheduling in Web Advertising'. Together they form a unique fingerprint.

Cite this