1

Streaming Algorithms for News and Scientific
Literature Recommendation: Submodular
Maximization with a d-Knapsack Constraint

arXiv:1603.05614v3 [cs.LG] 5 Jul 2016

Qilian Yu, Student Member, IEEE, Easton Li Xu, Member, IEEE, and Shuguang Cui, Fellow, IEEE

Abstract—Submodular maximization problems belong to the
family of combinatorial optimization problems and enjoy wide
applications. In this paper, we focus on the problem of maximizing
a monotone submodular function subject to a d-knapsack constraint,
for which
we propose a streaming algorithm that achieves


1
a 1+2d
−  -approximation of the optimal value, while it only
needs one single pass through the dataset without storing all the
data in the memory. In our experiments, we extensively evaluate
the effectiveness of our proposed algorithm via two applications:
news recommendation and scientific literature recommendation.
It is observed that the proposed streaming algorithm achieves
both execution speedup and memory saving by several orders of
magnitude, compared with existing approaches.

I. I NTRODUCTION
As our society enters the big data era, the main problem that data scientists are facing is how to process the
unprecedented large datasets. Besides, data sources are heterogenous, comprising documents, images, sounds, and videos.
Such challenges require the data processing algorithms to be
more computationally efficient. The concept of submodularity
plays an important role in pursuing efficient solutions for
combinatorial optimization, since it has rich theoretical and
practical features. Hence submodular optimization has been
adopted to preprocess massive data in order to reduce the
computational complexity. For example, in the kernel-based
machine learning [1], [2], the most representative subset of data
is first selected in order to decrease the dimension of the feature
space, by solving a submodular maximization problem under a
cardinality constraint. Besides, such submodular optimization
models have been extended to address data summarization
problems [3].
Although maximizing a submodular function under a cardinality constraint is a typical NP-hard problem, a simple
greedy algorithm developed in [4] achieves a (1 − e−1 )approximation of the optimal solution with a much lower
computation complexity. When the main memory can store the
whole dataset, such a greedy algorithm can be easily applied
for various applications. However, as it requires the full access
to the whole dataset, large-scale problems prevent the greedy
algorithm from being adequate due to practical computation
resource and memory limitations. Even in the case when the
memory size is not an issue, it is possible that the number of
Q. Yu, E. L. Xu, and S. Cui are with the Department of Electrical and
Computer Engineering, Texas A&M University, College Station, TX 77843
USA (e-mails: {yuql216, eastonlixu, cui}@tamu.edu).

data samples grows rapidly such that the main memory is not
able to read all of them simultaneously.
Under the scenarios discussed above, processing data in a
streaming fashion becomes a necessity, where at any time
point, the streaming algorithm needs to store just a small
portion of data into the main memory, and produces the
solution right at the end of data stream. A streaming algorithm
does not require the full access to the whole dataset, thus
only needs limited computation resource. In [5], the authors
introduced a streaming algorithm to maximize a submodular
function under a cardinality constraint, where the cardinality
constraint is just a special case of a d-knapsack constraint [6]
with each weight being one. When each element has multiple
weights or there are more than one knapsack constraints, the
algorithm proposed in [5] is no longer applicable.
In this paper, we develop a new streaming algorithm to maximize a monotone submodular function, subject to a general
d-knapsack constraint. It requires
onlyone single pass through

1
the data, and produces a 1+2d
−  -approximation of the
optimal solution, for any

>
0.
In addition, the algorithm

b log b
only requires O
memory (independent of the dataset

d
log b
size) and O
computation per element with b being

the standardized d-knapsack capacity. To our knowledge, it
is the first streaming algorithm that provides a constant-factor
approximation guarantee with only monotone submodularity
assumed. In our experiments, compared with the classical
greedy algorithm developed in [7], the proposed streaming
algorithm achieves over 10,000 times running time reduction
with a similar performance.
The rest of this paper is organized as follows. In Section
II we introduce the formulation and related existing results.
In Section III we describe the proposed algorithms. In Section
IV we present two applications in news and scientific literature
recommendations. We draw the conclusions in Section V.
II. F ORMULATION AND M AIN R ESULTS
A. Problem Formulation
Let V = {1, 2, . . . , n} be the ground set and f : 2V →
[0, ∞) be a nonnegative set function on the subsets of V . For
any subset S of V , we denote the characteristic vector of S by
xS = (xS,1 , xS,2 , . . . , xS,n ), where for 1 ≤ j ≤ n, xS,j = 1,
if j ∈ S; xS,j = 0, otherwise. For S ⊆ V and r ∈ V , the
marginal gain of f with respect to S and r is defined to be
∆f (r|S) , f (S ∪ {r}) − f (S),

2

which quantifies the increase in the utility function f (S) when
r is added into subset S. A function f is submodular if it
satisfies that for any A ⊆ B ⊆ V and r ∈ V \ B, the
diminishing returns condition holds:
∆f (r|B) ≤ ∆f (r|A).
Also, f is said to be a monotone function, if for any S ⊆ V
and r ∈ V , ∆f (r|S) ≥ 0. For now, we adopt the common
assumption that f is given in terms of a black box that
computes f (S) for any S ⊆ V . In Sections III-A, III-B, III-C,
we will discuss the case when the submodular function is
independent [8] of the ground set V (i.e., for any S ⊆ V ,
f (S) depends on only S, not V \ S), and in Section III-D, we
will discuss the setting where the value of f (S) depends on
not only the subset S but also the ground set V .
Next, we introduce the d-knapsack constraint. Let b =
(b1 , b2 , . . . , bd )T be a d-dimensional budget vector, where for
1 ≤ i ≤ d, bi > 0 is the budget corresponding to the i-th
resource. Let C = (ci,j ) denote a d × n matrix, whose (i, j)-th
entry ci,j > 0 is the weight of the element j ∈ V with respect
to the i-th knapsack resource constraint. Then the d-knapsack
constraint can be expressed by CxS ≤ b. The problem for
maximizing a monotone submodular function f : 2V → [0, ∞)
subject to a d-knapsack constraint can be formulated as
maximize

f (S)

subject to

CxS ≤ b.

S⊆V

(1)

We aim to MAximize a monotone Submodular set function
subject to a d-Knapsack constraint, which is called d-MASK
for short. Without loss of generality, for 1 ≤ i ≤ d, 1 ≤ j ≤
n, we assume that ci,j ≤ bi . That is, no entry in C has a
larger weight than the corresponding knapsack budget, since
otherwise the corresponding element is never selected into S.
For the sake of simplicity, we here standardize Problem (1).
Let
b , max bi and c0 ,
min
bci,j /bi .
1≤i≤d

1≤i≤d,1≤j≤n

For 1 ≤ i ≤ d, 1 ≤ j ≤ n, we replace each ci,j with
bci,j /bi c0 and bi with b/c0 . We then create a new matrix D by
concatenating C and b over columns. That is, D = (di,j ) is a
d × (n + 1) matrix, such that, for 1 ≤ i ≤ d, di,j = ci,j ≥ 1 if
1 ≤ j ≤ n; di,j = b if j = n + 1. The standardized problem
has the same optimal solution as Problem (1). In the rest of
the paper, we only consider the standardized version of the
d-MASK problem.
B. Related Work and Main Results
Submodular optimization has been regarded as a powerful
tool for combinatorial massive data mining and machine learning, for which a streaming algorithm processes the dataset
piece by piece and then produces an approximate solution right
at the end of the data stream. This makes it quite suitable to
process a massive dataset in many applications.
When d = 1 and all entries of C are ones, Problem (1)
is equivalent to maximizing a monotone submodular function
under a cardinality constraint. This optimization problem has

been proved to be NP-hard [4], and people have developed
many approximation algorithms to solve this problem, among
which the greedy algorithm [4] is the most popular one.
Specifically, the greedy algorithm selects the element with
the maximum marginal value at each step and produces a
(1 − e−1 )-approximation guarantee with O(kn) computation
complexity, where k is the maximum number of elements that
the solution set can include, and n is the number of elements
in the ground set V . Recently, some accelerated algorithms
were proposed in [9], [10]. Unfortunately, neither of them can
be applied to the case when the size of the dataset is over
the capacity of the main memory. A streaming algorithm was
developed in [5] with a (1/2−)-approximation of the optimal
value, for any  > 0. This streaming algorithm does not require
the full access to the dataset, and needs only one pass through
the dataset. Thus it provides a practical way to process a large
dataset on the fly with a low memory requirement, but not
applicable under a general d-knapsack constraint.
Further, the authors in [11] dealt with the case when d = 1
and each entry of C can take any positive values. Maximizing
a monotone submodular function under a single knapsack
constraint is also called a budgeted submodular maximization
problem. This problem is also NP-hard, and the authors in [7]
suggested a greedy algorithm, which produces a (1 − e−1 )approximation of the optimal value with O(n5 ) computation
complexity. Specifically, it first enumerates all the subsets of
cardinalities at most three, then greedily adds the elements with
maximum marginal values per weight to every subset starting
with three elements, and finally outputs the suboptimal subset.
Although the solution has a (1−e−1 )-approximation guarantee,
the O(n5 ) computation cost prevents this greedy algorithm
from being widely used in practice. Hence some modified
versions of the greedy algorithm have been developed. The
authors in [11] applied it to document summarization with
a (1 − e−1/2 ) performance guarantee. In [12], the so-called
cost effective forward (CEF) algorithm for outbreak detection
was proposed, which produces a solution with a (1 − e−1 )/2approximation guarantee and requires only O(M n) computation complexity, where M is the knapsack budget when d = 1.
The considered d-MASK problem is a generalization of the
above problems to maximize a submodular function under
more than one budgeted constraints. A framework was proposed in [6] for maximizing a submodular function subject
to a d-knapsack constraint, which yields a (1 − e−1 − )approximation for any  > 0. However, it is hard to implement
this algorithm, since it involves some high-order terms with
respect to the number of budgets, making it inappropriate
for processing large datasets [13]. Later, an accelerated algorithm was developed in [14]. It runs for O (1/δ) rounds in
MapReduce [15] for a constant δ, and provides an Ω (1/d)approximation. However, this algorithm needs an O(log n)
blowup in communication complexity among various parts.
As observed in [16], such a blowup decreases its applicability
in practice. Note that the authors in [14] mentioned that the
MapReduce method with an Ω (1/d)-approximation can be
extended to execute in a streaming fashion, but did not provide
any concrete algorithms and the associated analysis.
Table I shows the comparison among the approximation

3

TABLE I.

C OMPARISON OF APPROXIMATION GUARANTEES AND COMPUTATION COSTS

1-Knapsack Constraint
d-Knapsack Constraint

Best Performance Known Algorithms
Approx. Factor
Comput. Cost
1 − e−1
O(n5 )
−1
1−e
−
Polynomial

guarantees and computation costs of the aforementioned algorithms against our proposed algorithm.
To our best knowledge, this paper is the first to propose
an efficient streaming algorithm for maximizing a monotone
submodular function under a d-knapsack constraint, with 1)
a constant-factor approximation guarantee, 2) no assumption
on full access to the dataset, 3) execution of a single pass, 4)
O(b log b) memory requirement, 5) O(log b) computation complexity per element, and 6) only assumption on monotonicity
and submodularity of the objective function. In the following
section, we describe the proposed algorithm in details.
III.

A. Special Case: One Cardinality Constraint
We first consider a special case of the d-MASK problem:
maximizing a submodular function subject to one cardinality
constraint:
S⊆V

O(n log b/)

Theorem 1. The simple streaming algorithm (Algorithm 1)
produces a solution S such that
f (S) ≥

α
OPT.
2

Proof: Given v ∈ [αOPT, OPT], let us discuss the
following two cases.
Case 1: |S| = k. For 1 ≤ i ≤ k, let ai be the element added
to S in the i-th iteration of the for-loop. Then we obtain

i=1

By the condition in Line 4 of Algorithm 1, for 1 ≤ i ≤ k, we
have
f ({a1 , a2 , . . . , ai }) − f ({a1 , a2 , . . . , ai−1 }) ≥

f (S)

subject to |S| ≤ k.

1/(1 + 2d) − 

f (S) = f ({a1 , a2 , . . . , ak }) ≥ f ({a1 , a2 , . . . , ak }) − f (∅)
k
X


=
f ({a1 , a2 , . . . , ai }) − f ({a1 , a2 , . . . , ai−1 }) .

S TREAMING A LGORITHMS FOR M AXIMIZING
M ONOTONE S UBMODULAR F UNCTIONS

maximize

Proposed Streaming Algorithms
Approx. Factor
Comput.Cost

(2)

In [4], the authors proved this problem is NP-hard and
proposed a classical greedy algorithm. At each step of the
algorithm, as we explained earlier, the element with the largest
marginal value is added to the solution set. This operation, in
fact, reduces the “gap” to the optimal solution by a significant
amount. Formally, if element j is added to the current solution
set S by the greedy algorithm, the marginal value ∆f (j|S) of
this picked element should be at least above certain threshold.
In [5], the authors developed the so-called Sieve-Streaming
algorithm, where the threshold for the marginal value is set to
be (OPT/2 − f (S))/(k − |S|), where S is the current solution
set, k is the maximum allowed number of elements in S,
and OPT is the optimal value of the optimization problem. In
our paper, for this submodular maximization problem under
a single cardinality constraint, we first introduce a simple
streaming algorithm under the assumption that we have the
knowledge of the optimal value of the problem.
Algorithm 1 Simple Streaming Algorithm
1: Input: v such that αOPT ≤ v ≤ OPT, for some α ∈ (0, 1].
2: S := ∅.
3: for j := 1 to n
v
and |S| ≤ k then
4:
if f (S ∪ {j}) − f (S) ≥ 2k
5:
S := S ∪ {j}.
6:
end if
7: end for
8: return S.

v
,
2k

and hence
f (S) ≥

α
v
· k ≥ OPT.
2k
2

Case 2: |S| < k. Let S̄ = S ∗ \S, where S ∗ is the optimal
solution to the Problem (2). For each element a ∈ S̄, we have
f (S ∪ {a}) − f (S) <

v
.
2k

Since f is monotone submodular, we obtain
f (S ∗ ) − f (S) = f (S ∪ S̄) − f (S)
X
v
1
≤
[f (S ∪ {a}) − f (S)] <
· k ≤ f (S ∗ ),
2k
2
0
a∈S

which implies that
f (S) >

1
α
1
f (S ∗ ) = OPT ≥ OPT.
2
2
2

This simple streaming algorithm produces a solution by
visiting every element in the ground set only once. But it
requires the knowledge of the optimal value of the problem.
Besides, when the elements have non-uniform weights, this
algorithm does not work. To deal with the problem with nonuniform weights and more than one constraint, we are going to
modify the greedy rule and take the weight-dependent marginal
values into account in a streaming fashion.

4

B. General Case: Multiple Knapsack Constraints
In order to get the desirable output, in this subsection,
we first assume we have some knowledge of OPT, and then
remove this assumption by estimating OPT based on the
maximum value per weight of any single element. At the end,
we will remove all assumptions to develop the final version
of the streaming algorithm for the general case of a d-MASK
problem.
Suppose that we know a value v such that αOPT ≤ v ≤
OPT for some 0 < α ≤ 1. That is, we know an approximation
of OPT up to a constant factor α. We then construct the
following algorithm to choose a subset S with the knowledge
of the optimal value of the problem.
Algorithm 2 OPT-KNOWN-d-MASK
1: Input: v such that αOPT ≤ v ≤ OPT, for some α ∈ (0, 1].
2: S := ∅.
3: for j := 1 to n
2v
4:
if ci,j ≥ 2b and f ({j})
ci,j ≥ b(1+2d) for some i ∈ [1, d]
then
5:
S := {j}.
6:
return S.
7:
endPif
∆f (j|S)
2v
≥ b(1+2d)
8:
if
for all
l∈S∪{j} ci,l ≤ b and
ci,j
i ∈ [1, d] then
9:
S := S ∪ {j}.
10:
end if
11: end for
12: return S.
At the beginning of the algorithm, the solution set S is set
to be an empty set. The algorithm will terminate when either
we find an element j ∈ V satisfying
ci,j ≥

b
f ({j})
2v
and
≥
for some i ∈ [1, d], (3)
2
ci,j
b(1 + 2d)

or we finish one pass through the dataset. Here we define that
an element j ∈ V is a big element if it satisfies (3). When
the algorithm finds a big element a, it simply outputs {a} and
terminates. The following lemma shows that {a} is already a
good enough solution.
Lemma 1. Assume the input v satisfies αOPT ≤ v ≤ OPT,
and V has at least one big element. The output S of Algorithm 2 satisfies
α
OPT.
f (S) ≥
1 + 2d
Proof: Let a be the first big element that Algorithm 2
finds. Then {a} is output and the algorithm terminates. Therefore, by (3), we have
f (S) = f ({a}) ≥

2v
b
v
α
· =
≥
OPT.
b(1 + 2d) 2
1 + 2d
1 + 2d

When V does not contain any big elements, during the data
streaming, an element j is added to the solution set S if 1)

the marginal value per weight for each knapsack constraint
∆f (j|S)/ci,j is at least βv/b for 1 ≤ i ≤ d, and 2) the overall
d-knapsack constraint is still satisfied. In this paper, we set
2b
β = 1+2d
, which gives us the best approximation guarantee
as shown in the proof of Theorem 2. The following lemma
shows the property of the output of Algorithm 2.
Lemma 2. Assume that V has no big elements. The output S
of Algorithm 2 has the following two properties:
1) There exists an ordering a1 , a2 , . . . , a|S| of the elements
in S, such that for all 0 ≤ t < |S| and 1 ≤ i ≤ d, we
have
∆f (at+1 |St )
2v
≥
,
(4)
ci,at
b(1 + 2d)
2)

where St = {a1 , a2 , . . . , at }.
P|S|
Assume that for 1 ≤ i ≤ d, t=1 ci,at ≤ b/2. Then
for each aj ∈ V , there exists an index µ(aj ), with
1 ≤ µ(aj ) ≤ d such that
2v
∆f (aj |S)
<
.
cµ(aj ),aj
b(1 + 2d)

Proof: 1) For 0 ≤ t < |S|, at the (t + 1)-th step of the
algorithm, assume that at+1 is the element added to the current
solution set St = {a1 , a2 , . . . , at }. Then a1 , a2 , . . . , a|S| forms
an ordering satisfying (4).
2) By contradiction, assume that there exists j ∈ V such
that for 1 ≤ i ≤ d, we have
2v
f (S ∪ {j}) − f (S)
.
≥
ci,j
b(1 + 2d)
Since j is not a big element and f is submodular, we have
ci,j < b/2, for 1 ≤ i ≤ d. Then j can be added into S, where
a contradiction occurs.
We then establish the following
theorem to show that Al
α
-approximation of the optimal
gorithm 2 produces an 1+2d
solution to Problem (1).
Theorem 2. Assuming that the input v satisfies αOPT ≤ v ≤
OPT, Algorithm 2 has the following properties:
α
• It outputs S that satisfies f (S) ≥ 1+2d
OPT;
• It only goes one pass over the dataset, stores at most
O(b) elements, and has O(d) computation complexity
per element.
Proof: If V contains at least one big element, by
Lemma 1, we have
α
OPT;
f (S) ≥
1 + 2d
otherwise, we
P discuss the following two cases:
Case 1:
j∈S ci,j ≥ b/2, for some i ∈ [1, d]. By the
submodularity of f and Property 1) in Lemma 2, we have
X
2v
v
α
f (S) ≥
ci,j ≥
≥
OPT.
b(1 + 2d)
1 + 2d
1 + 2d
j∈S
P
Case 2: j∈S ci,j < b/2, for all i ∈ [1, d]. Let Si∗ be the set
of elements aj ∈ S ∗ \S such that µ(aj ) = i, for 1 ≤ i ≤ d.

5

S
Then we have S ∗ \ S = 1≤i≤d Si∗ . With the help of the
submodularity of f and Property 2) in Lemma 2, we obtain
X
2v
2v
cµ(aj ),aj <
,
f (S ∪ Si∗ ) − f (S) ≤
b(1 + 2d)
1 + 2d
∗
aj ∈Si

for 1 ≤ i ≤ d. Then we have
f (S ∗ ) − f (S) = f (S ∪ (S ∗ \ S)) − f (S)
X
2dv
≤
[f (S ∪ Si∗ ) − f (S)] <
,
1 + 2d
1≤i≤d

and further,
1
2dv
≥
OPT.
1 + 2d
1 + 2d
In both cases, we conclude
α
OPT.
f (S) ≥
1 + 2d
f (S) > f (S ∗ ) −

Since we have ci,j ≥ 1 for all i ∈ [1, d], j ∈ [1, n], we store
at most O(b) elements during the algorithm. In the for-loop,
we compare the values at most d times. Then the computation
cost per element in the algorithm is O(d).
We can obtain an approximation of the optimal value
OPT by solving the d-MASK problem via Algorithm 2 .
But in certain scenarios, requiring the knowledge of an approximation to the optimization problem and utilizing the
approximation in Algorithm 2 lead to a chicken and egg
dilemma. That is, we have to first estimate OPT and then use
it to compute OPT. Fortunately, even in such scenarios, we
still have the following lemma to estimate OPT if we know
m , max1≤i≤d,1≤j≤n f ({j})/ci,j , the maximum value per
weight of any single element.

Setting v = [1 + (1 + 2d)]blog1+(1+2d) OPTc , we then obtain
m
1
≤
OPT ≤ v ≤ OPT ≤ bm,
1 + (1 + 2d)
1 + (1 + 2d)
and
1
v≥
OPT ≥ [1 − (1 + 2d)]OPT.
1 + (1 + 2d)
Based on Lemma 3, we propose the following algorithm
that gets around the chick and egg dilemma.
Algorithm 3 m-KNOWN-d-MASK
1: Input: m.
2: Q := {[1 + (1 + 2d)]l |l ∈ Z,
m
l
3:
1+(1+2d) ≤ [1 + (1 + 2d)] ≤ bm}.
4: for v ∈ Q
5:
Sv := ∅.
6: end for
7: for j := 1 to n
2v
8:
if ci,j ≥ 2b and f ({j})
ci,j ≥ b(1+2d) for some i ∈ [1, d]
then
9:
S := {j}.
10:
return S.
11:
end if
12:
for v ∈
PQ
∆ (j|S)
2v
13:
if l∈S∪{j} ci,l ≤ b and fci,j ≥ b(1+2d)
for all
i ∈ [1, d] then
14:
Sv := Sv ∪ {j}.
15:
end if
16:
end for
17: end for
18: S := argmax f (Sv ).
Sv ,v∈Q

Lemma 3. Let
n
Q = [1 + (1 + 2d)]l |l ∈ Z,
o
m
≤ [1 + (1 + 2d)]l ≤ bm
1 + (1 + 2d)
1
. Then there exists at least some
for some  with 0 <  < 1+2d
v ∈ Q such that [1 − (1 + 2d)]OPT ≤ v ≤ OPT.

Proof: First, choose i0 ∈ [1, d], j 0 ∈ [1, n] such that
f ({j })/ci0 ,j 0 = m. Since ci0 ,j 0 ≥ 1, we have
0

OPT ≥ f ({j 0 }) = mci0 ,j 0 ≥ m.
Also, let {j1 , j2 , . . . , jt } be a subset of V such that
f ({j1 , j2 , . . . , jt }) = OPT. Then by the submodularity of f ,
OPT = f (∅) +

t
X
[f ({j1 , j2 , . . . , ji }) − f ({j1 , j2 , . . . , ji−1 })]
i=1

t
X
≤ f (∅) +
[f ({ji }) − f (∅)]
i=1

≤

t
X
i=1

f ({ji }) ≤ m

t
X
i=1

c1,ji ≤ bm.

19:

return S.

Then we establish the following
 theorem
 to show that
1
the above algorithm achieves a 1+2d
−  -approximation




b
guarantee, and requires O b log
memory and O log b

computation complexity per element.
Theorem 3. With m known, Algorithm 3 has the following
properties:


1
• It outputs S that satisfies f (S) ≥ 1+2d
−  OPT;
• It goes one
stores
at most
 pass over the dataset,


b log b
log b
O
elements, and has O
computation
d

complexity per element.
Proof: By Lemma 3, we choose v ∈ Q such that
[1 − (1 + 2d)]OPT ≤ v ≤ OPT. Then by Theorem 2, the
output S satisfies


1 − (1 + 2d)
1
f (S) ≥
OPT =
−  OPT.
1 + 2d
1 + 2d
l
m
Notice that there are at most log1+(1+2d) b + 1 (of order
log b
d )

elements in Q. At the end of the algorithm, Sv with

6

the largest function value will be picked to be the output.
Since S contains
3 stores
at most b elements, Algorithm


log b
b log b
elements and has O
computation
at most O
d

complexity per element.
Introducing the maximum marginal value per weight m
avoids the chicken and egg dilemma in Algorithm 2. With
m known, Algorithm 3 needs only one pass over the dataset.
However, we need an extra pass through the dataset to obtain
the value of m. In the following, we will develop our final
one-pass streaming algorithm with m unknown.
Algorithm 4 d-KNAPSACK-STREAMING
1: Q := {[1 + (1 + 2d)ε]l |l ∈ Z}.
2: for v ∈ Q
3:
Sv := ∅.
4: end for
5: m := 0.
6: for j := 1 to n
2v
7:
if ci,j ≥ 2b and f ({j})
ci,j ≥ b(1+2d) for some i ∈ [1, d]
then
8:
S := {j}.
9:
return S.
10:
end if
11:
for i := 1 to d
12:
m := max{m, f ({j})/ci,j }.
13:
end for
14:
Q := {[1 + (1 + 2d)ε]l |l ∈ Z,
m
l
15:
1+(1+2d) ≤ [1 + (1 + 2d)ε] ≤ 2bm}.
16:
for v ∈
PQ
∆ (j|S)
2v
17:
if l∈S∪{j} ci,l ≤ b and fci,j ≥ b(1+2d)
for all
i ∈ [1, d] then
18:
Sv := Sv ∪ {j}.
19:
end if
20:
end for
21: end for
22: S := argmax f (Sv ).
Sv ,v∈Q

23:

return S.

We modify the estimation candidate set Q into {[1 + (1 +
m
2d)]l |l ∈ Z, 1+(1+2d)
≤ [1 + (1 + 2d)]l ≤ 2bm}, and maintain the variable m that holds the current maximum marginal
value per weight of all single element. During the data streaming, if a big element a is observed, the algorithm simply
outputs {a} and terminates. Otherwise, the algorithm will
update m and the estimation candidate set Q. If the marginal
value per weight for each knapsack constraint ∆f (j|S)/ci,j is
at least 2v/b(1 + 2d) for 1 ≤ i ≤ d, and the overall d-knapsack
constraint is still satisfied, then an element j is added to the
corresponding candidate set. Then we establish the following
theorem, which shows the property of the output of Algorithm
4. Its proof follows the same lines as the proof of Theorem 3.
Theorem 4. Algorithm 4 has the following properties:


1
• It outputs S that satisfies that f (S) ≥ 1+2d
−  OPT;
• It goes one pass over the dataset, stores at most





b
log b
O b log
elements,
and
has
O
computation
d

complexity per element.

C. Online Bound
To evaluate the performance of our proposed algorithms, we
need to compare the function values obtained by our streaming
algorithm against OPT, by calculating their relative difference.
Since OPT is unknown, we could use an upper bound of OPT
to evaluate the performance of the proposed algorithms.
By Theorem 4, we obtain
OPT ≤

1 + 2d
f (S).
1 − (1 + 2d)

(5)

1+2d
f (S) is an upper bound of the optimal value to
Then 1−(1+2d)
the d-MASK problem. In most of cases, this bound is not tight
enough. In the following, we provide a much tighter bound
derived by the submodularity of f .

Theorem 5. Consider a subset S ⊆ V . For 1 ≤ i ≤ d, let
ri,s = ∆f (s|S)/ci,s , and si,1 , . . . , si,|V \S| be the sequence
such that ri,si,1 ≥ ri,si,2 ≥ · · · ≥ ri,si,|V \S| . Let ki be the
Pki −1
Pki
integer such
≤ b and j=1
ci,si,j > b. And
i,j
j=1 ci,s.
 that
Pki −1
let λi = b − j=1 ci,si,j
ci,si,ki . Then we have
OPT = max f (S 0 ) ≤ f (S)
CxS0 ≤b


kX
i −1
+ min 
∆f (si,j |S) + λi ∆f (si,ki |S) .
1≤i≤d

(6)

j=1

Proof: Here we use a similar proof as the proof of
Theorem 8.3.3 in [17], where the author deals with the submodular maximization problem under one knapsack constraint.
Let S ∗ be the optimal solution to Problem (1). First we
consider the 1-MASK problem, which has the same objective
function as Problem (1) but only with the i-th knapsack
constraint. Assume Si∗ is its optimal solution. Since this 1MASK problem has fewer constraints than Problem (1), we
have f (S ∗ ) ≤ f (Si∗ ). Hence,
f (S ∗ ) ≤ min f (Si∗ ).
1≤i≤d

Since f is monotone submodular, for 1 ≤ i ≤ d,
X
f (Si∗ ) ≤ f (S ∪ Si∗ ) ≤ f (S) +
∆f (s|S).

(7)

(8)

s∈Si∗

We first assume that all weights ci,j and knapsack b are
rational numbers. For the i-th 1-MASK problem, we can
multiply all ci,j and b by the least common multiple of their
denominators, making each weight and budget be an integer.
We then replicate each element s in V into ci,s copies. Let
s0i denote any one copy of s, and let Vi0 and Si∗ 0 be the sets
of the copies of all elements in V and Si ∗ , respectively. Also,

7

define ∆0f (s0i |S) , ∆f (s|S)/ci,s . Then

X

X

∆f (s|S) =

s∈Si∗

∆0f (s0i |S)

s0i ∈Si∗ 0

≤

X

max
0
0

K 0 ⊆Vi ,|K |≤b

∆0f (s0i |S).

(9)

s0i ∈K 0

To find the value of the right-hand side of (9), we actually need
to solve a unit-cost modular optimization problem as follows.
We first sort all elements s0 in Vi0 such that the corresponding
values ∆0f (s0 |S) form a non-increasing sequence. In this
sequence, the first b elements
are ci,s copies of si,j for

Pki −1 i,j 
1 ≤ j ≤ ki − 1, and b − j=1 ci,si,j copies of si,ki .
Therefore, we obtain

max
0
0

X

K ⊆Vi 0
s ∈K 0
|K 0 |≤b i

∆0f (s0i |S) =

kX
i −1

∆f (si,j |S) + λi ∆(si,ki |S).

j=1

(10)

Combining (7), (8), (9) and (10), we obtain (6).

∞
For irrational weights and knapsacks, let ci,si,j ,t t=1 and
∞
{bt }t=1 be two rational sequences with limits ci,si,j and b,
respectively. And further let ki,t be the integer such that
Pki,t −1
Pki,t
ci,si,j ,t ≤ bt and j=1
ci,si,j ,t > bt , and let
j=1

Algorithm 5 Online Bound of the d-MASK Problem
1: Input: S.
2: for i := 1 to d
3:
Si0 := ∅.
4:
for s in V
5:
ri,s := ∆f (s|S)/ci,s .
6:
end for
P
6 ∅
7:
while {s ∈ V \ (S ∪ Si0 )| j∈S∪S 0 ∪{s} ci,j ≤ b} =
i
r
.
8:
s0 :=
argmax
i,s
P
9:
10:
11:

Si0

s∈V \(S∪Si0 ),
:= Si0 ∪ {s0 }.

end while
s0 :=

j∈S∪S 0 ∪{s}
i

ci,j ≤b

argmax

P
s∈V \(S∪Si0 ), j∈S∪S 0 ∪{s} ci,j ≤b

ri,s .

i
P
λi := (b − s∈S 0 ci,s )/ci,s0 .
i
P
13:
δi := s∈S 0 ∆f (s|S) + λi ∆f (s0 |S).
i
14: end for
15: return f (S) + min1≤i≤d δi .

12:

D. Problems with Ground-Set Dependent Submodular Functions
In the previous sections, we have discussed the case when
the submodular function f is independent of the ground set
V . In the following, we will discuss the setting where f is
additively decomposable [8], and the value of f (S) depends
on not only the subset S but also the ground set V . Here a
function f is called to be additively decomposable [8] over
|V |
the ground set V , if there exists a family of functions {fi }i=1
V
with fi : 2 → [0, ∞) independent of the ground set V such
that
1 X
fi (S).
(11)
f (S) =
|V |
i∈V



ki,t −1

λi,t = bt −

X

,
ci,si,j ,t 

ci,si,ki,t ,t .

j=1

∞

Then {λi,t }t=1 is a rational sequence with limit λi . According
to the above argument, we obtain for each t,

max f (S 0 ) ≤ f (S)


kX
i −1
∆f (si,j |S) + λi,t ∆f (si,ki |S) .
+ min 

CxS0 ≤b

1≤i≤d

j=1

Algorithm 4 is still useful for the case when f is dependent
on the ground set but additively decomposable. To reduce the
computational complexity, we randomly choose a small subset
Ve of V , and use
1 X
fVe (S) ,
fi (S)
e
|V | e
i∈V

instead of f in Algorithm 4. It can be proved that with a high
probability, we can still obtain a good approximation to the
optimal solution, when fi ’s are bounded. The accuracy of the
approximation is quantified by the following theorem.
Theorem 6. Assume that for S ⊆ V and 1 ≤ i ≤ n, |fi (S)| ≤
1. We uniformly choose a subset Ve from V , with
|Ve | ≥ 2−2 b2 (b log |V | + log(2/δ)) ,

By letting t go to infinity, we then finish the proof.
A bound is called to be offline [17] if it can be stated before
we run the algorithm; otherwise, it is an online one [17]. Here,
we obtain an offline bound (5) and an online bound (6), the
latter of which can be calculated by the following algorithm.

and use fVe instead of f in Algorithm 4. Then with probability
of at least 1 − δ, the output S of Algorithm 4 satisfies


1
−  (OPT − ).
fVe (S) ≥
1 + 2d

8

Its proof follows the similar argument as the proof of
Theorem 6.2 in [5], where the authors deal with the submodular maximization problem under one cardinality constraint.
Now we adopt a two-pass streaming algorithm for the dMASK problem with ground-set dependent submodular objective functions: in the first pass, we utilize reservoir sampling
[18] to sample an evaluation set Ve randomly; in the second
pass, we run Algorithm 4 with the objective function fVe
instead of f .
IV. A PPLICATIONS
In this section, we discuss two real-world applications for
Algorithm 4: news recommendation and scientific literature
recommendation.
A. News Recommendation
Nowadays, people are facing many news articles on the
daily basis, which highly stresses their limited reading time.
A news recommendation system helps people quickly fetch
the information they need. Specifically, it provides the most
relevant and diversified news to people by exploiting their
behaviors, considering their reading preferences, and learning
from their previous reading histories.
However, the vast amount of news articles in the dataset are
hard to be processed efficiently. In [19], the authors modeled
the user behavior as a submodular maximization problem.
Based on the learning result, a classical greedy algorithm [4]
was implemented to provide a set of relevant articles to the
users. However, the large amount of data in the dataset prevents
the classical greedy algorithm from producing the solution
in time due to its expensive computation cost. Besides, the
reading behavior of the users was oversimplified in [19], where
it is assumed that each user reads a fixed number of articles per
day. Since the time spent on different news articles varies, it is
more reasonable to use the number of words of the articles as
the measure of the reading behaviour. Hence, we can formulate
this question into a 1-MASK problem as follows:
f (S) = wT F(S)
X
subject to
cj ≤ b,
maximize
S⊆V

j∈S

where cj is the number of words in article j. Here F :
2V → [0, ∞)m , where m is the number of features. We
require the total number of words in the selected articles not
to exceed a specified budget b, due to the limitation of the
user reading time. In addition, we assume that the non-negative
parameter vector w is learnt by a statistical learning algorithm,
based on the historical user preference (three such learning
algorithms can be found in [19], [20], and [21], respectively).
Let (φ1 (d), . . . , φm (d)) be the characteristic vector of article d,
where for 1 ≤ j ≤ m, φj (d) = 1 if d has feature j, φj (d) = 0,
otherwise. We then define F(S) = (F1 (S), . . . , Fm (S)); here
for 1 ≤ j ≤ m, Fj (S) is the aggregation function of S with
respect to feature j and defined by
!
X
Fj (S) , log 1 +
φj (s) .
s∈S

Fig. 1. Comparison of Utilities and Computation Costs between the Greedy
Algorithm and Streaming Algorithm

This choice of function Fj guarantees both precision and
coverage of the solution set. On one hand, the monotonicity of
Fj (S) encourages feature j to be selected if its corresponding
weighting parameter wj (the j-th coordinate of the vector w)
is relatively large. On the other hand, the diminishing return
property of Fj prevents too many items with feature j from
being selected.
Notice that function Fj is a monotone submodular function.
To see this, let
X
Gj (S) ,
φj (s).
s∈S

Obviously, Gj (S) is a non-decreasing modular function. With
the fact that ζ(x) , log(1 + x) is an increasing concave
function, we can conclude that Fj (S) = ζ(Gj (S)) is a
monotone submodular function. Since both monotonicity and
submodularity are closed under the non-negative linear combinations [22], f is a monotone submodular function as well.
The solution based on Algorithm 4 to this 1-MASK problem
provides the user a quick news recommendation.
As an illustration, we analyze the dataset collected in [23],
which contains over 7, 000 feedback entries from 25 people
with around 8, 000 news articles. We set m = 480 and
b = 20, with each entry of C randomly chosen from a
uniform distribution over {1, 2, 3, 4, 5}. The learning algorithm
proposed in [19] is used to calculate w. We then compare
Algorithm 4 with the greedy algorithm in [7].
In Fig. 1, we set the objective function value obtained by
the classical greedy algorithm and its computation time both
to be 1, after using them to normalize the function value and
computation time corresponding to our streaming algorithm,
respectively. It has been shown that our streaming algorithm
achieves 94% utility of the greedy algorithm, but only requires
a tiny fraction of the computation cost. Thus the proposed
algorithm works well in the news recommendation system and
is practically useful over large datasets.
B. Scientific Literature Recommendation
Next, we introduce an application in scientific literature
recommendation. Nowadays, the researchers have to face an
enormous amount of articles and collect information that they

9

Let W (a)Pbe a pre-assigned weight to each vertex a ∈ A
such that a∈A W (a) = 1. Then our goal is to minimize the
expected penalty
X
π(S) ,
W (a) min{T (S, a), Tmax },
a∈A

or maximize the expected penalty reduction
X
R(S) , Tmax − π(S) =
W (a)[Tmax − T (S, a)]+ ,
a∈A

Fig. 2.

An Example of Citation Networks

are interested in, where they have to filter the massive existing
scientific literatures and pick the most useful ones. A common
approach to locate the targeted literatures is based on the socalled citation networks [24]. The authors in [24] mapped a
citation network onto a rating matrix to filter research papers.
In [25], an algorithm utilizing the random-walker properties
was proposed. It transforms a citation matrix into a probability
transition matrix and outputs the entries with the highest biased
PageRank scores.
We here propose a new scientific literature recommendation
system based on the citation networks and the newly proposed
streaming algorithm (Algorithm 4). Consider a directed acyclic
graph G = (V, E) with V = {1, 2, . . . , n}, where each vertex
in V represents a scientific article. Let Ri denote the number
of references contained in article i. The arcs between papers
represent their citation relationship. For two vertices i, j ∈ V ,
arc (i, j) ∈ E if and only if paper i cites paper j. The
information spreads over the reverse directions of the arcs.
As an example, Fig. 2 presents a citation network, which
contains six vertices and seven arcs. Each of six papers cites
a certain number of references. The information initiates from
a set of vertices (source papers), and then spreads across the
network. Let A be the collection of the source papers. Our
target is to select a subset S out of V to quickly detect the
information spreading of A. For example, A = {1, 3, 4} in
Fig. 2. If we choose S = {6}, we can detect the source papers
1, 3, 4 by paths 6 → 4 → 1, 6 → 3 and 6 → 4, respectively.
This problem can be formulated as a monotone submodular
maximization under a 3-knapsack constraint1 :
maximize
S⊆V

R(S)

subject to CxS ≤ b,

(12)

where C = (ci,j ) is a 3 × n matrix and b = (b1 , b2 , b3 )T .
Observe that the papers in A transfer their influence through
the citation network, but this influence becomes less as it
spreads through more hops. Let T (s, a) be the length of the
shortest directed path from s to a. Then the shortest path length
from any vertex in S to a is defined as
T (S, a) , min T (s, a).
s∈S

1 The reason why we set d = 3 will be explained later in this section;
based on the different usages, the number of knapsack constraints and the
corresponding budgets can be changed accordingly.

where [x]+ , max{x, 0} and Tmax is a given maximum
penalty. Note that R is a monotone submodular function.
To see this, for two subsets B ⊆ C ⊆ V , we have
T (B, a) ≥ T (C, a) for any a ∈ A, such that R(B) ≤ R(C);
Tmax − T (S, a) is a submodular function with respect to S
since
T (B, a) − T (B ∪ {v}, a) = [T (B, a) − T (v, a)]+
≥ [T (C, a) − T (v, a)]+ = T (C, a) − T (C ∪ {v}, a),
with v ∈ V \ C. Then R(S) is also submodular, since it is a
convex combination of Tmax − T (S, a) for a ∈ A.
We construct three constraints in (12) from the aspects
of recency, biased PageRank score, and reference number
respectively. The first aspect is from the fact that readers prefer
to read the recently published papers. Let c1,j be the time
difference between the publishing date of paper j and the
current date, and b1 be the corresponding limit.
For the second aspect, the classical PageRank algorithm [26]
could be used to compute an important score for every vertex
in the graph: a vertex will be assigned a higher score if it is
connected to a more important vertex with a lower out-degree.
The authors in [25] introduced a so-called biased PageRank
score. It is a measure of the significance of each paper, not
only involving the propagation and attenuation properties of
the network, but also taking the set of source vertices into
account. Let ρ(j) be the biased PageRank score of article j.
1
We further choose a function ξ(x) , 1 + 1+x
to map the
PageRank score onto (1, 2]. Then paper j with the smaller
value c2,j , ξ(ρ(j)) is more valuable for the researchers. Also
we set b2 to be corresponding budget.
Thirdly, we assume that more references listed in the paper,
more time the reader spends on picking the valuable information. Then we set c3,j to be the number Rj of references in
paper j and b3 be the budget of the total number of references.
To evaluate the performance of Algorithm 4, for scientific
literature recommendation, we utilize a dataset collected in
[27]. This dataset includes more than 20,000 papers in the
Association of Computational Linguistics (ACL). There are
two methods to evaluate the performance of an algorithm for
literature recommendation: online evaluation and offline evaluation. In the online evaluation, some volunteers are invited
to test the performance of the recommendation system and
express their opinions. Here we use the offline evaluation
to compare the function values obtained by our proposed
algorithm (Algorithm 4) and the PageRank algorithm proposed
in [25].

10

We perform the sensitive analysis over different knapsack
constraints. With the other two constraints fixed, we change
the value of the budget corresponding to the recency, biased
PageRank score or reference number, respectively. Here we
randomly select five nodes as the source papers. We set
Tmax = 50 and W (a) = 0.2 for each source paper a. The
results for the optimal objective values are shown in Fig. 3
(with fixed b2 = 10, b3 = 20), Fig. 4 (with fixed b1 = 20,
b3 = 20) and Fig. 5 (with fixed b1 = 20, b2 = 10),
respectively. It can be observed that the relative difference
is around 10% between the function values obtained by our
streaming algorithm (blue lines) and the corresponding online
bounds (red lines).

biased PageRank algorithm as shown in Figs. 3, 4 and 5,
respectively. Although the biased PageRank algorithm suggests
the papers with high biased PageRank scores, most of the
suggested papers have very long distances from the set of
source articles (even disconnected from the source papers in
some cases), which leads to a very low objective function
value.
V.

C ONCLUSIONS

In this paper, we proposed a streaming algorithm to maximize a monotone submodular
function

 under a d-knapsack
1
constraint. It leads to a 1+2d
−  approximation of the
optimal value, and requires only a single pass through the
dataset and a small memory size. It achieves a major fraction
of the utility function value obtained by the greedy algorithm
with a much lower computation cost, which makes it very
practically implementable. Our algorithm provides a more
efficient way to solve the related combinatorial optimization
problems, which could find many good applications, such as
in news and scientific literature recommendations as shown in
the paper.
ACKNOWLEDGEMENT

Fig. 3.
Optimal Function Values corresponding to Different Recency
Constraints

We thank Dr. Nao Kakimura for comments that greatly
improved the manuscript.
R EFERENCES
[1]

[2]

[3]

Fig. 4. Optimal Function Values corresponding to Different Biased PageRank
Constraints

[4]

[5]

[6]

[7]

[8]
Fig. 5.
Optimal Function Values corresponding to Different Reference
Knapsack Constraints

Also, we find that our algorithm highly outperforms the

[9]

H. Lin and J. Bilmes, “How to Select a Good Training-data Subset for
Transcription: Submodular Active Selection for Sequences,” Proc. 2009
Annu. Conf. Int. Speech Commun. Assoc., Brighton, UK, Sept. 2009.
Y. Liu, K. Wei, K. Kirchhoff, Y. Song, and J. Bilmes, “Submodular
Feature Selection for High-dimensional Acoustic Score Spaces,” Proc.
2013 IEEE Int. Conf. Acoust. Speech Signal Process., pp. 7184–7188,
May 2013.
S. Chakraborty, O. Tickoo, and R. Iyer, “Adaptive Keyframe Selection
for Video Summarization,” Proc. 2015 IEEE Winter Conf. Applicat.
Comput. Vision, pp. 702–709, Waikoloa, HI, Jan. 2015.
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An Analysis of
Approximations for Maximizing Submodular Set Functions–I,” Math.
Program., vol. 14, no. 1, pp. 265–294, Dec. 1978.
A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause,
“Streaming Submodular Maximization: Massive Data Summarization
on the Fly”, Proc. 20th ACM SIGKDD Int. Conf. Knowl. Discov. Data
Mining, pp. 671–680, New York, NY, Aug. 2014.
A. Kulik, H. Shachnai, and T. Tamir, “Maximizing Submodular Set
Functions subject to Multiple Linear Constraints,” Proc. 20th Annu.
ACM-SIAM Symp. Discrete Algor., pp. 545–554, New York, NY, Jan.
2009.
M. Sviridenko, “A Note on Maximizing a Submodular Set Function
subject to a Knapsack Constraint,” Oper. Res. Lett., vol. 32, pp. 41–43,
Jan. 2004.
B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, “Distributed
Submodular Maximization: Identifying Representative Elements in
Massive Data,” Proc. 2013 Adv. Neural Inf. Process. Syst., pp. 2049–
2057, Dec. 2013.
A. Badanidiyuru, Ashwinkumar, and J. Vondrák, “Fast Algorithms
for Maximizing Submodular Functions,” Proc. 25th Annu. ACM-SIAM
Symp. Discrete Algor., pp. 1497–1514, Portland, OR, Oct. 2014.

11

[10]

[11]

[12]

[13]
[14]

[15]

[16]

[17]
[18]
[19]

[20]

[21]

[22]
[23]

[24]

[25]

[26]

[27]

B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák, and
A. Krause, “Lazier than Lazy Greedy,” Proc. 29th AAAI Conf. Artif.
Intell., pp. 1812–1818, Austin, TX, Jan. 2015.
H. Lin and J. Bilmes, “Multi-document Summarization via Budgeted
Maximization of Submodular Functions,” Proc. 2010 NAACL HLT, pp.
912–920, Los Angeles, CA, June 2010.
J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and
N. Glance, “Cost-effective Outbreak Detection in Networks,” Proc. 13th
ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, pp. 420–429,
San Jose, CA, Aug. 2007.
G. Papachristoudis, “Theoretical Guarantees and Complexity Reduction
in Information Planning,” Ph.D. Dissertation, MIT, June 2015.
R. Kumar, B. Moseley, S. Vassilvitskii, and A. Vattani, “Fast Greedy
Algorithms in MapReduce and Streaming,” Proc. 25th Annu. ACM
Symp. Parallelism Algor. Archit., pp. 1–10, Montreal, QC, June 2013.
J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing
on Large Clusters,” Proc. 6th USENIX Symp. Oper. Syst. Design
Implement., pp. 137–150, San Francisco, CA, Dec. 2004.
R. Kiveris, S. Lattanzi, V. Mirrokni, V. Rastogi, and S. Vassilvitskii,
“Connected Components in MapReduce and Beyond,” Proc. ACM
Symp. Cloud Comput., pp. 1–13, Seattle, WA, June 2014.
J. Leskovec, “Dynamics of Large Networks,” Ph.D. Dissertation,
Carnegie Mellon Univ., Sept. 2008.
J. S. Vitter, “Random Sampling with a Reservoir,” ACM Trans. Math.
Softw., vol. 11, no. 1, pp. 37–57, Mar. 1985.
K. Raman, P. Shivaswamy, and T. Joachims, “Online Learning to
Diversify from Implicit Feedback,” Proc. 18th ACM SIGKDD Int. Conf.
Knowl. Discov. Data Mining, pp. 705–713, Beijing, China, Aug. 2012.
L. Li, D. Wang, T. Li, D. Knox, and B. Padmanabhan, “Scene:
A Scalable Two-stage Personalized News Recommendation System,”
Proc. 34th Annu. Int. ACM SIGIR Conf., pp. 125–134, Beijing, China,
July 2011.
W. IJntema, F. Goossen, F. Frasincar, and F. Hogenboom, “Ontologybased News Recommendation,” Proc. 2010 EDBT/ICDT Workshops, pp.
1–6, Lausanne, Switzerland, Mar. 2010.
S. Fujishige, Submodular Functions and Optimization, 2nd ed., Amsterdam, Netherlands: Elsevier, Sept. 2005.
S. R. Shawn and Y. Zhang, “Interaction and Personalization of Criteria
in Recommender Systems,” User Modeling, Adaptation, and Personalization, pp. 183–194, Springer, June 2010.
S. M. McNee, I. Albert, D. Cosley, P. Gopalkrishnan, S. K. Lam, A.
Rashid, J. A. Konstan, and J. Riedl, “On the Recommending of Citations
for Research Papers,” Proc. 2002 ACM Conf. Comput. Support. Coop.
Work, pp. 116–125, New Orleans, LA, Nov. 2002.
M. Gori and A. Pucci, “Research Paper Recommender Systems: A
Random-walk Based Approach,” Proc. 2006 IEEE/WIC/ACM Int. Conf.
Web Intell., pp. 778–781, Dec. 2006.
L. Page, S. Brin, R. Motwani, and T. Winograd, “The PageRank Citation
Ranking: Bringing Order to the Web,” Technical Report, Stanford Univ.,
Jan. 1998.
M. T. Joseph and D. R. Radev, “Citation Analysis, Centrality, and the
ACL Anthology,” Technical Report CSE-TR-535-07, Oct. 2007.

