Name
Abstract | ||
|---|---|---|
This paper is concerned with online story scheduling, motivated by storyboarding in online advertising. In storyboarding, triggered by the browsing history of a user, advertisers arrive online and wish to present a sequence of ads (stories) on the website. The user ceases to browse with probability 1-β at each time step. Once the user finishes watching an ad, the advertiser derives a reward. The goal of the website is to determine a schedule that maximizes the expected total reward. This problem was first introduced by Dasgupta et al.(SODAu002709) [7], and then improved by Alberts and Passen (ICALPu002713) [4]. In this paper, we abandon the preemptive assumption in [7] and [4], and consider a more realistic setting: online non-preemptive story scheduling, i.e., a running job (correspond to advertiseru0027 story) cannot be preempted even if another job leads to a higher reward.Specifically, we study the setting where only 1-lengthed and k-lengthed ads are allowed. We first present a greedy algorithm which achieves a competitive ratio of βk-1, and prove that this ratio is optimal for deterministic algorithms. Then, we propose a randomized algorithm with a competitive ratio of 1 over k+1 for general β, and then show that no randomized algorithm can achieve a competitive ratio better than (1+(1-βk-1)kover(1-βk)k-1)-1. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.5555/2936924.2936965 | AAMAS |
Field | DocType | Citations |
Pluralistic walkthrough,Randomized algorithm,Nonpreemptive multitasking,Advertising,Scheduling (computing),Computer science,Online advertising,Greedy algorithm,Mechanism design,Artificial intelligence,Competitive analysis | Conference | 0 |
PageRank | References | Authors |
0.34 | 18 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tie-yan Liu | 1 | 4662 | 256.32 |
| Weidong Ma | 2 | 45 | 1.81 |
| Tao Qin | 3 | 2384 | 147.25 |
| Pingzhong Tang | 4 | 133 | 32.06 |
| Guang Yang | 5 | 17 | 3.33 |
| Bo Zheng | 6 | 5 | 1.77 |