Online story scheduling in web advertising

ABSTRACT

We study an online job scheduling problem motivated by storyboarding in web advertising, where an advertiser derives value from uninterrupted sequential access to a user surfing the web. The user ceases to browse with probability 1 -- β at each step, independently. Stories (jobs) arrive online; job s has length l_s and per-unit value v_s. A value v_s is obtained for every unit of the job that is scheduled consecutively without interruption, discounted for the time at which it is scheduled. Jobs can be preempted, but no further value can be derived from the residual unscheduled units of the job. We seek an online algorithm whose total reward is competitive against that of the offline scheduler that knows all jobs in advance.

We consider two models based on the maximum delay that can be allowed between the arrival and scheduling of a job. In the first, a job can be scheduled anytime after its arrival; in the second a job is lost unless scheduled immediately upon arrival, preempting a currently running job if needed. The two settings correspond to two natural models of how long an advertiser retains interest in a relevant user. We show that there is, in fact, a sharp separation between what an online scheduler can achieve in these two settings. In the first setting with no deadlines, we give a natural deterministic algorithm with a constant competitive ratio against the offline scheduler. In contrast, we show that in the sharp deadline setting, no (deterministic or randomized) online algorithm can achieve better than a polylogarithmic ratio.

REFERENCES

• 1: S. Ben-David, A. Borodin, R. Karp, G. Tardos, and A. Wigderson, On the Power of Randomization in On-Line Algorithms. Algorithmica, 11(1): 2--14, 1994.
• 2: Avrim Blum , Shuchi Chawla , David R. Karger , Terran Lane , Adam Meyerson , Maria Minkoff, Approximation Algorithms for Orienteering and Discounted-Reward TSP, SIAM Journal on Computing, v.37 n.2, p.653-670, May 2007 [doi>10.1137/050645464]
• 3: Ran Canetti , Sandy Irani, Bounding the Power of Preemption in Randomized Scheduling, SIAM Journal on Computing, v.27 n.4, p.993-1015, Aug. 1998 [doi>10.1137/S0097539795283292]
• 4: Mohammad T. Hajiaghayi, Online auctions with re-usable goods, Proceedings of the 6th ACM conference on Electronic commerce, p.165-174, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064027]
• 5: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 6: A. W. Kolen, J. K. Lenstra, C. H. Papadimitriou, and F. C. Spieksma. Interval scheduling: A survey. Naval Research Logistics, 54:530--543, 2007.
• 7: Ron Lavi , Noam Nisan, Online ascending auctions for gradually expiring items, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 8: marketingterms.com. Surround sessions. http://www.marketingterms.com/dictionary/surround_session.
• 9: Ryan Porter, Mechanism design for online real-time scheduling, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988783]
• 10: Pricewaterhouse Coopers. IAB internet advertising revenue report. http://www.iab.net/media/file/IABPwC2007fullyear.pdf.
• 11: N. Y. Times. What is surround sessions? http://nytimes.com/ads/marketing/surroundsessions.
• 12: Gerhard J. Woeginger, On-line scheduling of jobs with fixed start and end times, Theoretical Computer Science, v.130 n.1, p.5-16, Aug. 1, 1994 [doi>10.1016/0304-3975(94)90150-3]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation