Online Optimization of Video-Ad Allocation

1 Introduction

Internet advertising is one of the main marketing tools today. According to one report [Interactive Advertising Bureau, 2015], the annual revenue in 2014 from internet advertisements (hereafter "ads") in the US was $49.5 billion, which was higher than the total revenue from radio, newspapers, and magazines. Internet ads have also attracted attention from the research community. Numerous computation problems arising from internet advertising have been studied (e.g., [Radovanovic and Heavlin, 2012; Bhalgat et al., 2012; Bharadwaj et al., 2012; Bhalgat et al., 2014; Ieong et al., 2014; Bateni et al., 2014; Balseiro et al., 2014; Hojjat et al., 2014]), and the results from these studies constitute a rich area in computer science.

Among the many kinds of internet display ads, this paper focuses on video-ads. Nowadays video advertising is often used in video streaming services, and it is a rapidly growing industry. One study [Pew Research Center, 2014] estimates that video advertising will make up 15% of the total internet advertising market by 2017. To our knowledge, however, computation problems related to video advertising have not yet been investigated.

∗This work was supported by JST ERATO Grant Number JPMJER1201, Japan, and JSPS KAKENHI Grant Number JP16K16005.

A difference between video-ads and traditional display ads is that the former need to consider the time to be viewed by a user. Each video-ad has a time length, and video-ads need to be watched for a certain amount of time to influence users. This is in contrast to traditional display ads. Moreover, the time spent watching video-ads depends on the user's particular situation and interest. When long video-ads for sporting goods are allocated to someone who is busy and uninterested in sports, this user is likely to stop watching the video and leave the website. On the other hand, a user who is not busy and likes sports is likely to watch such video-ads for sporting goods. In addition, this user may watch more than one ad. Indeed, some video streaming services show several ads in succession to a user who is going to watch a long video, such as a movie and a TV show. However, these two factors-the length of a video-ad and the time spent watching it by usershave not been considered in previous studies on display advertising. Hence, algorithms to optimize ad-allocations for traditional display ads are inefficient for video-ads. Motivated by this observation, this paper offers an initial study of the optimization of video-ad allocations.

1.1 Our Contributions

The aim of this paper is to design efficient algorithms for deciding video-ad allocation. Our contributions are summarized as follows:

• We formulate the video-ad allocation problem, which is an extension of the ad-auction problem introduced by Mehta et al. [2007].
• We present an online algorithm for the video-ad allocation problem, by showing that the video-ad allocation problem is included by a general online allocation framework proposed by Goel et al. [2010]. In addition, we analyze the dependence of its competitive ratio on the ratio of bids to budgets of advertisers, which was ignored in the analysis of Goel et al.
• We also consider envy-free pricing and user-dependent video-lengths in the video-ad allocation problem for more practical modeling. To obtain a (1 - 1/e)- competitive algorithm for this setting, we extend the framework of Goel et al.

Formulation of the Video-Ad Allocation Problem

We formulated the video-ad allocation problem, which extends the so-called ad-auction problem proposed by Mehta et al. [2007] for traditional display advertising. The ad-auction problem is an online optimization problem of allocating ads to users arriving at sites one-by-one so that the total revenue from advertisers is maximized. When a user arrives, all advertisers submit a price (or "bid") that they are willing to pay to show his ad to the user. Only one advertiser wins the auction to be assigned to the user. Each advertiser has a budget, and they cannot pay beyond the remaining budget. Mehta et al. proposed a (1 - 1/e)-competitive online algorithm for the ad-auction problem under the small bid assumptioni.e., each bid is relatively smaller than the associated budgets. Their analysis uses a technique called factor-revealing linear programming (LP). Subsequently, Buchbinder et al. [2007] proposed another (1 - 1/e)-competitive online algorithm based on the primal-dual method.

For the video-ad allocation problem, we introduce two factors to the ad-auction problem: video length and viewing time. Each advertiser has a video-ad with its length, and each user has a viewing limit (or "capacity") representing the extent of that user's viewing time. We assume that we know the viewing capacity on arrival of a user. While the ad-auction problem allocates only one ad to each user's ad slot, the video-ad allocation problem can show more than one video-ad to each user in succession in the user's ad slot. For simplicity, we first assume that a user watches allocated video-ads to the end, as long as the total length of the ads does not exceed the user's viewing capacity. This constraint has the same structure as the knapsack problem, which is a classical optimization problem. This makes the problem much more difficult than the ad-auction problem.

Relationship with the Framework of Goel et al.

We present an online algorithm for the video-ad allocation problem. The main ingredient in this algorithm is a general framework of the ad-auction problem proposed by Goel et al. [2010] in a context of the ad-auction problem with the generalized second-price scheme. In their model, it is allowed to allocate more than one ad to a single user. Instead, the input of the problem specifies sets of ads (called feasible allocation) which can be assigned to a user and an associated pricing scheme. Supposing that an algorithm for computing a maximumweight feasible set is available, Goel et al. gave an online primal-dual algorithm for this general online problem. Its competitive ratio is 1 - 1/e under the small bid assumption. We note that the framework of Goel et al. includes the ad-auction problem, and hence the algorithm of Goel et al. extends the algorithm of Buchbinder et al. [2007].

To apply the algorithm of Goel et al. to the video-ad allocation problem, we have to show that a maximum weight feasible set can be computed. Indeed, in the video-ad allocation problem, this computation is equivalent to solving the knapsack problem. This observation indicates that the video-ad allocation problem admits a (1 - 1/e)-competitive algorithm under the small bid assumption.

We also analyze the dependence of the competitive ratio of the algorithm on the ratio of bids to budgets of advertisers.

Let Rmax denote the maximum of ratio of a bid to a budget over all advertisers and their bids to users. The small bid assumption demands that Rmax is almost 0. To explain precisely, the competitive ratios of algorithms in [Buchbinder et al., 2007; Mehta et al., 2007; Goel et al., 2010] depend on Rmax, and approach 1 - 1/e when Rmax approaches 0. Goel et al. did not describe how the competitive ratio of their algorithm depends on Rmax explicitly. We present an explicit description of this dependence.

Envy-Free Pricing and User-Dependent Video Lengths

We also consider envy-free pricing in the video-ad allocation problem. In this setting, we are required to decide pricing for each advertiser together with a video-ad allocation. A pair of a pricing and an allocation is called envy-free if the payment of each advertiser is at most those of advertisers with longer allocated ads.

In addition, we assume that the length of a video depends on users. The purpose of this assumption is to model the preferences of users on the video topics. For instance, a user who prefers sports over cosmetics watches videos about sports more likely than ones about cosmetics. We incorporate this phenomenon by assuming that the length of a video is shorter if a user prefers it. If the length is shorter, then a user watches the video more likely because of the capacity constraint.

To deal with this extended setting, we generalize the framework of Goel et al. While the framework of Goel et al. assumes that the payment of each advertiser is decided from the allocated ads, the payments should also be decision variables in the envy-free pricing. Hence, in our new framework, we assume that feasible pairs of allocation and pricing are specified, and design an online primal-dual algorithm under the assumption that a maximum weight feasible pair can be computed. The competitive ratio of this algorithm is 1 - 1/e if the small bid assumption holds.

1.2 Organization

The remainder of this paper is organized as follows. Section 2 introduces the video-ad allocation problem, and explains its relationship with Goel et al. Section 3 presents and analyzes our algorithm for the setting with envy-free pricing. Section 4 evaluates our algorithms through computational experiments. Finally, Section 5 concludes the paper.

2 Video-ad Allocation Problem

2.1 Setting

Let N = {1, . . . , n} be a set of n advertisers. Each advertiser i ∈ N has a budget Bi and a video-ad that is ti in length. Further, let M = {1, . . . ,m} be a set of m users. Each user j ∈ M has a viewing capacity Tj, representing the extent of time where the user will allow the publisher to show video-ads. Users arrive one-by-one; below, we assume that j denotes the jth arriving user. Upon the arrival of a user j, each advertiser i submits a bid bij , and an online algorithm allocates a set Sj of advertisers to user j. The allocation is required to satisfy the following capacity constraints which demands that the total ad length from advertisers in Sj does not exceed the viewing capacity of user j-i.e., ∑i∈Sj ti ≤ Tj for each j ∈ M.

When an advertiser i is allocated to user j, then i pays bij from the advertiser's budget. For any user j, the publisher allocates only ads of those who have enough budgets to pay the bids. When the allocation to each user j is represented by the advertiser set Sj ⊆ N, the payment of an advertiser i is ∑j∈M:i∈Sj bij. The objective of the algorithm is to maximize the total revenue after all users in M arrive-i.e., ∑i∈N ∑j∈M:i∈Sj bij. We assume without loss of generality that each bid bij is smaller than the budget Bi, and define Rmax as maxi∈N,j∈M bij/Bi (≤ 1).

We take the adversarial input model, where an online algorithm decides the allocation to a user j without information regarding users arriving after j. When an algorithm computes an allocation by using all information about users, it is called offline. Let ALG and OPT denote the revenue for an online algorithm and the best offline algorithm, respectively. For β ≤ 1, the online algorithm is referred to as β-competitive if ALG ≥ β · OPT for any instance. Accordingly, β denotes the competitive ratio for an online algorithm if β is the maximum number such that the algorithm is β-competitive.

The ad-auction problem studied by [Buchbinder et al., 2007; Mehta et al., 2007] corresponds to the special case with ti = 1, i ∈ N and Tj = 1, j ∈ M.

2.2 General Framework of Goel et al.

Goel et al. [2010] introduced an abstract online problem that includes the ad-auction problem. In this subsection, we introduce this problem, and show that the video-ad allocation problem is included in it.

First, we give the problem definition. We are given sets of advertisers and users, where we denote the former by N and the later by M. Each user j specifies a subfamily Cj of 2N that comprises feasible allocations of ads to user j. We are also given a budget Bi of each advertiser i ∈ N and a bid bij for each advertiser i ∈ N and user j ∈ M, but the length ti of video-ads and the viewing capacity Tj of users are not given here. The problem seeks to find Sj ∈ Cj for each j ∈ M such that ∑j∈M:i∈Sj bij ≤ Bi for each i ∈ N. The objective is to maximize ∑j∈M ∑i∈Sj bij.

Goel et al. presented an online algorithm for this problem, assuming that following two conditions hold for each j ∈ M:

• Cj is subset-closed-i.e., if X ⊆ Y ∈ Cj, then X ∈ Cj;
• given any non-negative weights δi of advertisers i ∈ N, there exists an algorithm for finding S ∈ Cj that maximizes ∑i∈S δi.

The competitive ratio of their algorithm is 1 - 1/e under the small bid assumption.

The video-ad allocation problem is included in this problem. This can be seen by setting Cj = {S ∣∣ ∑i∈S ti ≤ Tj }. With this definition, Cj is downward-closed. Moreover, the problem of finding S ∈ Cj that maximizes ∑i∈S δi is equivalent to the knapsack problem, and hence it admits a (1 - ϵ)- approximation polynomial-time algorithm for any ϵ > 0 and an exact pseudo-polynomial time algorithm, whose running time depends on n and Tj. This fact indicates the following theorem.

Theorem 1. Under the small bid assumption, the video-ad allocation problem admits a polynomial-time (1 - 1/e - ϵ)- competitive algorithm for any constant ϵ > 0, and a pseudopolynomial time (1 - 1/e)-competitive algorithm.

Although the competitive ratio given in the above depends on Rmax, Goel et al. did not describe how it depends on Rmax explicitly. In the subsequent section, we analyze the competitive ratio of an algorithm that extends the one of Goel et al., describing its dependence on Rmax.

3 Envy-Free Pricing and User-Dependent Video Lengths

3.1 Setting

In this section, we discuss an envy-free pricing setting. Here, on arrival of a user, we decide both the allocation of video-ads and the pricing, i.e., the charge for each allocated advertiser.

Fix a user j ∈ M. We denote the charge for an advertiser i ∈ N by pi. Then, when user j arrives, an online algorithm is required to decide a pair of a pricing p and a video-ad allocation S ⊆ N. This pair is feasible in the envy-free setting if (i) ∑i∈S ti ≤ Tj, (ii) pi ≤ bij for each i ∈ N, (iii) pi = 0 for any i ̸∈ S, and (iv) pi ≥ pi′ for any i, i′ ∈ S with ti ≥ ti′ (the envy-freeness).

In addition, we suppose that the length of an video-ad depends on users to model the phenomenon that a user watches a video more likely if it is about his/her favorite topic. Hence, in this section, we let tij denote the length of an ad i when it is assigned to a user j. We use this user-dependent length in the capacity constraints (i.e., constraint ∑i∈S ti ≤ Tj is replaced by ∑i∈S tij ≤ Tj) while the envy-freeness is defined with regard to the original length.

3.2 New Framework

To deal with envy-free pricing, we generalize the framework of Goel et al. by introducing the concept of outcomes. For a nonnegative vector p ∈ RN+ and a set S ⊆ N, we say that (p, S) is an outcome, meaning that pi is the charge to advertiser i ∈ N and S is the allocation.

In our framework, a set Cj of feasible outcomes is specified for each j ∈ M. We suppose that Cj satisfies the following properties:

• Cj is subset-closed-i.e., for any (p, S) ∈ Cj and S′ ⊆ S, it holds (p′ , S′ ) ∈ Cj, where p′ ∈ RN+ is defined by p′i = pi for i ∈ S′ and p′i = 0 for i ∈ N \ S′ ;
• we can obtain an α-approximate solution (p, S) of

In this section, the definition of Rmax is modified to Rmax =max{pi/Bi | i ∈ N, j ∈M, (p, S) ∈ Cj}.

The envy-free pricing setting can be captured by this new framework by setting Cj as follows:

It is not difficult to see that this Cj is subset-closed. The following lemma presents a pseudo-polynomial time algorithm for finding an outcome that attains the maximum in (1), i.e., the second property required for Cj is satisfied with α = 1.

Lemma 1. If Cj is defined by (2), there exists a pseudopolynomial time algorithm for finding (p, S) ∈ Cj that achieves the maximum in (1) for any δi ∈ [0, 1], i ∈ N.

Proof. Recall that N = {1, . . . , n}. We assume without loss of generality that t1 ≤ · · · ≤ tn. For each i, k ∈ N and t ∈ {1, . . . , Tj}, define v(i, k, t) as the maximum discounted revenue ∑i∈N δipi achieved by (p, S) ∈ Cj such that S ⊆ {1, . . . , i}, all advertisers are charged at most bkj (i.e., pi′ ≤ bkj for all i′ ∈ N), and the total length of allocated video-ad is at most t (i.e., ∑i′∈S ti′ j ≤ t). In other words, v(i, k, t) is

Note that (1) = maxk∈N v(n, k, T). Let p(i, k, t) and S(i, k, t) be the pricing and the allocation achieving v(i, k, t). For convention, let v(i, k, t) = 0, S(i, k, t) = ∅, and p(i, k, t)i′ = 0, i′ ∈ N if i = 0 or if t ≤ 0.

Let i ∈ N. If S(i, k, t) does not contain ad i, then we have S(i, k, t) = S(i - 1, k, t), p(i, k, t)i = 0, p(i, k, t)i′ = p(i-1, k, t)i′ for i′ ∈ N \ {i}, and v(i, k, t) = v(i-1, k, t). If S(i, k, t) contains ad i and bij ≥ bkj, then we have S(i, k, t) = S(i - 1, k, t - tij) ∪ {i}, p(i, k, t)i = bkj, p(i, k, t)i′ = p(i - 1, k, t - tij)i′ for i′ ∈ N \ {i}, and v(i, k, t) = v(i - 1, k, t - tij) + δibkj . If S(i, k, t) contains ad i and bij < bkj , then we have S(i, k, t) = S(i - 1, i, t - tij) ∪ {i}, p(i, k, t)i = bij , p(i, k, t)i′ = p(i - 1, i, t - tij)i′ for i′ ∈ N \ {i}, and v(i, k, t) = v(i - 1, i, t - tij) + δibij , since prices of ads 1, . . . , i - 1 are at most the price of ad i. Because of this case analysis, we obtain a recursive formula of v(i, k, t) as follows: if bkj ≤ bij, then

A similar formula holds also for S(i, k, t) and p(i, k, t). Therefore, we can calculate v(i, k, t), S(i, k, t), and p(i, k, t) for all i, k, and t in O(n2Tj) time.

3.3 Algorithm

In this subsection, we present an algorithm for the framework defined in the previous section. We notice that Cj is an arbitrary set of outcomes that satisfy the above two properties in the following discussion.

For an outcome c ∈ Cj , we let Sc and pc denote the allocation and pricing in c, respectively. Our algorithm is based on the following LP relaxation:

For each integer feasible solution for (4), there is a corresponding feasible allocation for the video-ad allocation problem, and they achieve the same objective value in their own problems. Hence, the optimal objective value of (4) is an upper bound on the maximum revenue.

The dual of (4) is written as

Owing to the strong duality of LPs, the optimal objective value of (4) is equal to the optimal objective value of (5).

Our algorithm simultaneously constructs both an integer solution x feasible for (4) and a solution (y, z) feasible for (5). To prove that the algorithm is β-competitive, it suffices to show that these solutions satisfy

When our algorithm is invoked, yi is initialized to 0 for all i ∈ N. When a user j arrives, the algorithm computes an α-approximate solution c∗j for maxc∈Cj ∑i∈N pci(1 - yi). Without loss of generality, we assume that

The outcome c′j assigned for j is defined as the one obtained from c∗j by canceling the allocation of advertisers whose remaining budgets exceeds the assigned prices. Then the algorithm sets zj to the sum of ∑i∈N pc∗j i(1 - yi)/α. Updating yi depends on a parameter γ = (1+Rmax/α)1/Rmax (> 1). Note that γ approaches e1/α as Rmax approaches 0. For every advertiser i ∈ N, we update yi by

where y(j) i denotes yi at the end of the process of user j.

All details of our algorithm are described in Algorithm 1. Recall that user j denotes the one who arrives at the jth round.

The following theorem is the main result in this section.

Theorem 2. The competitive ratio of Algorithm 1 is α(1 - 1/γ)(1 - Rmax).

Notice that the competitive ratio approaches α(1-1/e1/α) as Rmax approaches 0. This together with Lemma 1 indicates that Algorithm 1 is a pseudo-polynomial time (1 - 1/e)- competitive algorithm for the problem in Section 3.1 under the small bid assumption. Since each round j takes O(n2Tj) time and Tj is small (say, 30) in practice, the algorithm runs fast enough. We prove Theorem 2 by showing the following:

• x = [xc,j ]⊤j∈M,c∈Cj computed by Algorithm 1 is feasible for (4),
• y = [y(m) 1 · · · y(m) n ]⊤, and z = [z1 · · · zm]⊤ computed by Algorithm 1 constitute a feasible solution for (5),

Algorithm 1: Online algorithm for allocating outcomes

It is not difficult to prove the first two facts, and hence we focus on the proof for the last fact in this article due to the space constraint. First, we show that when advertiser i does not have an enough budget to pay the bid at some round, then the algorithm does not allocate i to subsequent users. The following lemma is proven by a similar proof to the one used in [Buchbinder et al., 2007], and hence we omit the proof.

Since the algorithm avoids advertisers with little remaining budgets from Sc∗j , the algorithm may miss chances to gain more revenue. However, the following lemma shows that such budgetary loss is not considerable compared to the revenue of the algorithm.

Proof of Theorem 2. We denote by OPT and ALG the best revenue for the offline algorithms and the revenue for Algorithm 1, respectively. Let Dj be the objective values for the solution to (5) computed by Algorithm 1 at the end of the jth round-i.e., Dj = ∑i∈N Biy(j) i + ∑j ′≤j zj ′ . Since (y, z) is feasible for (5), OPT ≤ Dm holds.

We bound Dm by ALG. For j = 0, we have D0 = 0. By the construction of y(j) i and zj at the jth round of the algorithm, Dj -Dj-1 = ∑i∈N Bi(y(j) i - y(j-1) i ) + zj = γ α(γ-1) ∑i∈N pc∗j i holds for each j ≥ 1. Therefore, we have OPT ≤ Dm = γ α(γ-1) ∑i∈N ∑j∈M pc∗j i ≤

4 Experiments

We evaluate performance of Algorithm 1 through computational experiments. The algorithm is compared with a greedy algorithm (called Greedy) and a primal-dual algorithm (called PD) obtained by modifying the one proposed by Buchbinder et al. [2007] for the ad-auction problem. These two algorithms compute an allocation to user j as follows:

Greedy: Find a set S of advertisers in argmaxS∈Sj ∑i∈S bij , and allocate advertisers in S to user j.

In the envy-free pricing setting, Greedy computes an allocation and a pricing by dynamic programming, ignoring the past budget consumptions of advertisers. PD computes an optimal pricing after deciding an allocation as above.

4.1 Results for Artificial Instances

First, we evaluate the performance of the algorithms over randomly generated instances. Each instance is generated as follows. We choose the number n of advertisers from 25, 50, and 100, and the number m of users from 500, 1000, and 2000. We assume two distributions of budgets: (1) uniform distribution (Bi = 200 for all i ∈ N), or (2) Pareto distribution (the minimum possible value is 100 and the mean is 200). Each bid bij is picked uniformly at random from [0, 3]. Thus, Rmax ≤ 3/100. We assume that the length of each video-ad is same for any users, and hence the length of video-ad of advertiser i is written by ti. Each ti is generated uniformly at random from [10, 45], and capacity Tj from [10, 60].

Table 1 shows average revenues of each algorithm for each set of n, m, and the budget distribution. The average is taken over 100 instances for each parameter set. Here, "standard" means the standard setting of the video-ad allocation problem, and "envy-free" means the envy-free pricing setting of the problem. Figures 1a and 1b plot the revenue of each algorithm over the number of users for two typical random instances with n = 25 and uniform distribution.

As shown in Table 1, our algorithm outperforms the other two algorithms in most of the cases. The Greedy performs well when the number m of users is small. In this case, most revenue advertisers still have enough budgets at the end. It is also observed from Figures 1a and 1b that the performance of our algorithm is same as the Greedy algorithm when m is small. However, the Greedy algorithm falls behind as budgets of advertisers are exhausted. The performance of the PD algorithm is worst when m is small, and it is still worse than our algorithm as a whole. When m is large, level-offs occurred. In this situation, almost all advertisers exhausted the budgets.

To demonstrate the superiority of our algorithm, we also compare the algorithms on a carefully constructed instance. In this instance, parameters are set so that n = 1110, m = 300, and Rmax = 0.01. All users have capacity 10. The user set is divided into U1 and U2 so that |U1| = 100 and |U2| = 200. Users in U1 arrive first, and then the others arrive. The budget of each advertiser is 100, and the advertisers are divided into three groups A1, A2, A3. The first group A1 consists of 10 advertisers with ti = 1 and bij = 1 for all users j. The second group A2 consists of 1000 advertisers with ti = 1, bij = 1 - ε for j ∈ U1, and bij = 0 for the others. The third group A3 consists of 100 advertisers with ti = 10, bij = 1 for j ∈ U1, and bij = 0 for the others.

On this instance, results do not change for the standard and the envy-free settings. Figure 2 shows the revenues of the algorithms. In this instance, the Greedy algorithm spends all budgets of advertisers in A1 for users in U1, and it obtains no revenue after that. The PD algorithm obtains revenue 1 per user in U1, while our algorithm gains revenue at least 10(1 - ε) per user. Observe that the final revenues of the algorithms are significantly different in this instance.

4.2 Results for Instances with a Real Dataset

In this subsection, we report results on an instance constructed from a real dataset. The dataset consists of browsing records of video-ads in a streaming site operated by Yahoo! JAPAN. Each record contains information on which users (distinguished by browser cookie) watched which ads. The dataset also includes the length of each video-ad, an approximate value of each budget, and viewing time of each user. There were 82 ads and 21,306,810 queries in our dataset. The streaming service sometimes allocated two ads to a query from a user. Such cases occurred on about 10% out of queries. From this dataset, we construct a problem instance as follows. We construct a set of n = 82 advertisers and a set of m = 21,306,810 users. We set the budget Bi for i ∈ N and the viewing time Tj for j ∈ M according to the dataset. The average of Tj is 18 seconds. Each bid from advertisers with no user preference is set to 2. If an advertiser input user preference, its bid for users satisfying the preference is set to an integer chosen randomly from [2, 10]. We also set the video length tij for advertiser i and user j from the user preference input by the advertisers and the browsing history of users, which we omit the details due to space limitation.

The results are described in Table 2. Here, each cell denotes the ratio (%) of revenue to total budget of all advertisers or total computational time. We can observe that the revenues of the proposed algorithm are better than the other algorithms by more than 1%. Moreover, the total computational times are short enough as it takes about 0.1ms per user.

Let us summarize experimental results. First, the Greedy algorithm performs best in the beginning of inputs, where no advertiser exhausts the budget. Our algorithm performs as well as the Greedy even in the beginning, and does better at the end. The PD algorithm gains more revenues than the Greedy at the end. However, since the PD is based on a greedy method for the knapsack problem, its revenue is sometimes significantly small compared with our algorithm. Our algorithm outperforms the others in most cases, including real-data instances. In addition, our algorithm can respond to each user quickly enough in practical settings. Therefore, our algorithm is practically useful.

5 Conclusion

In this paper, we formulated a new optimization problem, which models an important step of video-ad advertising, and presented an online algorithm with theoretical performance guarantee for it. There are many interesting directions of future studies on this topic. One direction is to predict users' viewing capacities. Our algorithms suppose that the viewing capacity of each user is revealed upon the user's arrival. For user experiences and effective advertisement, it is an important future work to develop a method for this estimation.