Submodular maximization with uncertain knapsack capacity
Yasushi Kawase

arXiv:1803.02565v1 [cs.DS] 7 Mar 2018

Tokyo Institute of Technology, Tokyo, Japan. Email: kawase.y.ab@m.titech.ac.jp
Hanna Sumita
National Institute of Informatics, Tokyo, Japan. JST, ERATO, Kawarabayashi Large Graph
Project. Email: sumita@nii.ac.jp
Takuro Fukunaga
RIKEN Center for Advanced Intelligence Project, Tokyo, Japan.
Email: takuro.fukunaga@riken.jp

Abstract
We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint.
Speciﬁcally, the problem is discussed in the situation that the knapsack capacity is not given explicitly and can be
accessed only through an oracle that answers whether or not the current solution is feasible when an item is added
to the solution. Assuming that cancellation of the last item is allowed when it overﬂows the knapsack capacity, we
discuss the robustness ratios of adaptive policies for this problem, which are the worst case ratios of the objective
values achieved by the output solutions to the optimal objective values. We present a randomized policy of robustness
ratio (1 − 1/e)/2, and a deterministic policy of robustness ratio 2(1 − 1/e)/21. We also consider a universal policy
that chooses
items following a precomputed sequence. We present a randomized universal policy of robustness ratio
√
(1 − 1/ 4 e)/2. When the cancellation is not allowed, no randomized adaptive policy achieves a constant robustness
ratio. Because of this hardness, we assume that a probability distribution of the knapsack capacity is given, and
consider computing a sequence of items that maximizes
√ the expected objective value. We present a polynomial-time
randomized algorithm of approximation ratio (1 − 1/ 4 e)/4 − ǫ for any small constant ǫ > 0.

1 Introduction
The submodular maximization is one of the most well-studied combinatorial optimization problems. Since it captures
an essential part of decision-making situations, it has a huge number of applications in diverse areas of computer
science. Nevertheless, the standard setting of the submodular maximization problem fails to capture several realistic
situations. For example, let us consider choosing several items to maximize a reward represented by a submodular
function subject to a resource limitation. When the amount of the available resource is exactly known, this problem is
formulated as the submodular maximization problem with a knapsack constraint. However, in many practical cases,
precise information on the available resource is not given. Thus, algorithms for the standard submodular maximization
problem cannot be applied to this situation. Motivated by this fact, we study robust maximization of submodular
functions with an uncertain knapsack capacity. Besides the practical applications, it is interesting to study this problem
because it shows how much robustness can be achieved for an uncertain knapsack capacity in submodular maximization.
More speciﬁcally, we study the submodular maximization problem with an unknown knapsack capacity (SMPUC).
In this problem, we are given a set I of items, and a monotone nonnegative submodular function f : 2 I → R+ such
that f (∅) = 0, where each item i ∈ I is associated with a size s(i). The objective is to ﬁnd a set of items that maximizes
the submodular function subject to a knapsack constraint, but we assume that the knapsack capacity is unknown. We
have access to the knapsack capacity through an oracle; we add items to the knapsack one by one, and we see whether
1

or not the selected items violates the knapsack constraint only after the addition. If a selected item ﬁts the knapsack,
the selection of this item is irrevocable. When the total size of the selected items exceeds the capacity, there are two
settings according to whether or not the last selection can be canceled. If the cancellation is allowed, then we remove
the last selected item from the knapsack, and continue adding the remaining items to the knapsack. In the other setting,
we stop the selection, and the ﬁnal output is deﬁned as the item set in the knapsack before adding the last item.
For the setting where the cancellation is allowed, we consider an adaptive policy, which is deﬁned as a decision tree
to decide which item to pack into the knapsack next. A randomized policy is a probability distribution over adaptive
policies. Performance of an adaptive policy is evaluated by the robustness ratio deﬁned as follows. For any number
C ∈ R+ , let OPTC denote the optimal item set when the capacity is C, and let ALGC denote an output of the policy.
Note that if the policy is a randomized one, then ALGC is a random variable. We call the adaptive policy α-robust,
for some α ≤ 1, if for any C ∈ R+ , the expected objective value of the policy’s output is within a ratio α of the optimal
value, i.e., E[ f (ALGC )]/ f (OPTC ) ≥ α. We also call the ratio α the robustness ratio of the policy.
One main purpose of this paper is to present algorithms that produce adaptive policies of constant robustness ratios
for SMPUC. Moreover, we consider a special type of adaptive policy called a universal policy. A universal policy
selects items following a precomputed order of items regardless of the observations made while packing. Thus, a
universal policy is identiﬁed with a sequence of the given items. This is in contrast to general adaptive policies, where
the next item to try can vary with the observations made up to that point. We present an algorithm that produces a
randomized universal policy that achieves a constant robustness ratio.
If the cancellation is not allowed, then there is no diﬀerence between adaptive and universal policies because the
selection terminates once a selected item does not ﬁt the knapsack. In this case, we observe that no randomized
adaptive policy achieves a constant robustness ratio. Due to this hardness, we consider a stochastic knapsack capacity
when the cancellation is not allowed. In this situation, we assume that the knapsack capacity is determined according
to some probability distribution and the information of the distribution is available. Based on this assumption, we
compute a sequence of items as a solution. When the knapsack capacity is realized, the items in the preﬁx of the
sequence are selected so that their total size does not exceed the realized capacity. The objective of the problem is
to maximize the expected value of the submodular function f for the selected items. We address this problem as the
submodular maximization problem with a stochastic knapsack capacity (SMPSC). We say that the approximation ratio
of a sequence is α (≤ 1) if its expected objective value is at least α times the maximum expected value of f for any
instance. The sequence computed in an α-robust policy for SMPUC achieves an α-approximation ratio for SMPSC.
However, the opposite does not hold, and an algorithm of a constant approximation ratio may exist for SMPSC even
though no randomized adaptive policy achieves a constant robustness ratio for SMPUC. Indeed, we present such an
algorithm.

1.1 Related studies
There are a huge number of studies on the submodular maximization problems (e.g., [18]), but we are aware of no
previous work on SMPUC or SMPSC. Regarding studies on the stochastic setting of the problem, several papers
proposed concepts of submodularity for random set functions and discussed adaptive policies to maximize those
functions [2, 10]. There are also studies on the submodular maximization over an item set in which each item is
activated stochastically [1, 9, 12]. However, as far as we know, there is no study on the problem with stochastic
constraints.
When the objective function is modular (i.e., the function returns the sum of the values associated with the selected
items), the submodular maximization problem with a knapsack constraint is equivalent to the classic knapsack problem.
For the knapsack problem, there are numerous studies on the stochastic sizes and rewards of items [5, 11, 15]. This
problem is called the stochastic knapsack problem. Note that this is diﬀerent from the knapsack problem with a
stochastic capacity (KPSC), and there is no direct relationship between them. However, we observe that most of the
algorithms for the stochastic knapsack problem can be applied to KPSC. Indeed, one of our algorithms for SMPSC is
based on the idea of Gupta et al. [11] for the stochastic knapsack problem.
The covering version of KPSC is studied in a context of single machine scheduling with nonuniform processing
speed. This problem is known to be strongly NP-hard [13], which implies that pseudo-polynomial time algorithms
are unlikely to exist. This is in contrast to the fact that the classic knapsack problem and its covering version admit
pseudo-polynomial time algorithms. Megow and Verschae [17] gave a PTAS for the covering version of KPSC.
To the best of our knowledge, KPSC itself has not been studied well. The only previous study we are aware of is
the thesis of Dabney [4], wherein a PTAS is presented for the problem. Since the knapsack problem and its covering

2

Table 1: Summary of main results in this paper

unknown
capacity
stochastic
capacity

with cancellation

without cancellation

rand. adaptive (1 − 1/e)/2-robust
√
rand. universal (1 − 1/ 4 e)/2-robust
det. adaptive 2(1 − 1/e)/21-robust

no constant robustness ratio
rand. pseudo-poly time (1/4 − o(1))-approx.
√
rand. ((1 − 1/ 4 e)/4 − ǫ)-approx.

version are equivalent in the existence of exact algorithms, the strongly NP-hardness of the covering version implies
the same hardness for KPSC.
Regarding the knapsack problem with an unknown capacity (KPUC), Megow and Mestre [16] mentioned that no
deterministic policy achieves a constant robustness ratio when cancellation is not allowed. They presented an algorithm
that constructs for each instance a policy whose robustness ratio is arbitrarily close to the one of an optimal policy
that achieves the largest robustness ratio for the instance. When cancellation is allowed, Disser et al. [6] provided a
deterministic 1/2-robust universal policy for KPUC. They also proved that no deterministic adaptive policy achieves
a robustness ratio better than 1/2, which means that the robustness ratio of their deterministic universal policy is best
possible even for any deterministic adaptive policy.

1.2 Contributions
Contributions in this paper are summarized in Table 1. For the case where cancellation is allowed, we present three
polynomial-time algorithms for SMPUC. These algorithms produce
• a randomized adaptive policy of robustness ratio (1 − 1/e)/2 (Section 3.1);

• a deterministic adaptive policy of robustness ratio 2(1 − 1/e)/21 (Section 3.2);
√
• a randomized universal policy of robustness ratio (1 − 1/ 4 e)/2 (Section 3.3).

Our algorithms are constructed based on a simple greedy algorithm [14] for the monotone submodular maximization
problem with a knapsack constraint. The greedy algorithm outputs a better solution among two candidates, one of
which is constructed greedily based on the increase in the objective function value per unit of size, and the other of
which is based on the increase in the objective function value. In our randomized adaptive policy, we achieve the
robustness ratio (1 − 1/e)/2 by guaranteeing that each of the two candidate solutions is output by our policy with
probability 1/2.
We convert this randomized policy into a deterministic one by mixing the two strategies which correspond to the
two candidate solutions. We remark that the same approach is taken for KPUC to construct a deterministic 1/2-robust
universal policy by Disser et al. [6]. They call an item swap item if it corresponds to a single-item solution for some
knapsack capacity. A key idea in their policy is to pack swap items earlier than the others. However, their technique
fully relies on the property that the objective function is modular, and their choice of swap items is not suitable
for SMPUC. In the present paper, we introduce a new notion of single-valuable items. This enables us to design a
deterministic 2(1 − 1/e)/21-robust policy. We remark that our proof technique is also diﬀerent from the standard one
used in related work. Moreover, we modify the randomized adaptive policy to obtain the randomized universal policy.
A key idea here is to guess a capacity by a doubling strategy.
We also show that no randomized adaptive policy achieves a robustness ratio better than 8/9 for KPUC (Section 4.1).
It is known that the robustness ratio achieved by deterministic policies for this problem is at most 1/2 [6], but there was
no upper bound on the robustness ratio for randomized policies. Disser et al. [6] mentioned that it is an interesting open
problem to improve the ratio 1/2 by randomized policies. Our upper bound implies that, even if randomized policies
are considered, the ratio cannot be
√improved better than 8/9. In addition, we show that no deterministic policy√achieves
robustness ratio better than (1 + 5)/4 and no randomized policy achieves robustness ratio better than (5 + 5)/8 for
SMPUC even when each item has a unit size (Section 4.3).
When cancellation is not allowed, it has been already known that KPUC admits no deterministic universal policy
of a constant robustness ratio [16]. We advance this hardness result by showing that no randomized adaptive policy
achieves a constant robustness ratio (Section 4.2).
3

For SMPSC without cancellation, we present the following two algorithms:
• a pseudo-polynomial time randomized algorithm of approximation ratio 1/4 − o(1) (Section 5.1);
√
• a polynomial-time randomized algorithm of approximation ratio (1 − 1/ 4 e)/4 − ǫ for any small constant ǫ > 0
(Section 5.2).
The former algorithms is based on the observation that the problem can be reduced to the submodular maximization
problem with an interval independent constraint. The latter algorithm is based on the idea of Gupta et al. [11] for the
stochastic knapsack problem. Gupta et al. regarded the knapsack capacity as a time limit, and showed that a rounding
algorithm for a time-index linear program (LP) gives an adaptive policy for the stochastic knapsack problem. Although
the formulation size of the time-index LP is not polynomial, a simple doubling technique reduces the formulation size
to polynomial with a loss of the approximation ratio. In our algorithm for SMPSC, we ﬁrst introduce a time-index
convex relaxation of the problem using the multilinear extension of the objective function, and show that the rounding
algorithm of Gupta et al. is a monotone contention resolution scheme for any realization √
of the knapsack capacity.
This observation gives a pseudo-polynomial time algorithm of approximation ratio (1 − 1/ 4 e)/2 − o(1) for SMPSC.
We then transform it into a polynomial-time algorithm. This transformation requires a careful sketching of knapsack
capacity, which was not necessary for the stochastic knapsack problem.

1.3 Organization
The rest of this paper is organized as follows. Section 2 gives notations and preliminary facts used in this paper.
Section 3 presents the adaptive policies for SMPUC with cancellation. Section 4 provides the upper-bounds on
the robustness ratios. Section 5 presents the approximation algorithms for SMPSC without cancellation. Section 6
concludes the paper.

2 Preliminaries
In this section, we deﬁne terminologies used in this paper, and introduce existing results which we will use.
Maximization of monotone submodular functions: The inputs of the problem are a set I of n items and a
nonnegative set function f : 2 I → R+ . In this paper, we assume that (i) f satisﬁes f (∅) = 0, (ii) f is submodular (i.e.,
f (X) + f (Y) ≥ f (X ∪ Y ) + f (X ∩ Y) for any X, Y ⊆ I), and (iii) f is monotone (i.e., f (X) ≤ f (Y) for any X, Y ⊆ I
with X ⊆ Y). The function f is given as an oracle that returns the value of f (X) for any query X ⊆ I. Let I ⊆ 2I be
any family such that X ⊆ Y ∈ I implies X ∈ I. The I-constrained submodular maximization problem seeks X ∈ I
that maximizes f (X).
We focus on the case where I corresponds to a knapsack constraint. Namely, each item i ∈ I is associated with a
Í
C > 0. We assume that the item
size s(i), and I is deﬁned as {X ⊆ I : i ∈X s(i) ≤ C} for some knapsack capacity
Í
size s(i) (i ∈ I) and the knapsack capacity C are positive integers. We denote i ∈X s(i) by s(X) for any X ⊆ I.

Problem SMPUC: In SMPUC, the knapsack capacity C is unknown. We can see whether an item set ﬁts the knapsack
only when an item is added to the item set.
A solution for SMPUC is an adaptive policy P, which is represented as a binary decision tree that contains every
item at most once along each path from the root to a leaf. Each node of the decision tree is an item to try packing
into the knapsack. A randomized policy is a probability distribution over binary decision trees. One of the decision
trees is selected according to the probability distribution. For a ﬁxed capacity C, the output of a policy P is an item
set denoted by P(C) ⊆ I obtained as follows. We start with P(C) = ∅ and check whether the item r at the root of
P ﬁts the knapsack, i.e., whether s(r) + s(P(C)) ≤ C. If the item ﬁts, then we add r to P(C) and continue packing
recursively with the left subtree of r. Otherwise, we have two options: when cancellation is allowed, we discard r and
continue packing recursively with the right subtree of r; when cancellation is not allowed, we discard r and output
P(C) to terminate the process.
When a policy does not depend on the observation made while packing, we call such a policy universal. Since
every path from the root to a leaf in a universal policy is identical, we can identify a universal policy with a sequence
Π = (Π1, . . . , Πn ) of items in I. For a ﬁxed capacity C, the output of a universal policy, denoted by Π(C), is constructed
as follows. We start with Π(C) = ∅, and add items to π(C) in n iterations. In the ith iteration, we check whether
4

s(Π(C)) + s(Πi ) ≤ C holds or not. If true, then Πi is added to X. Otherwise, Πi is discarded, and we proceed to the
next iteration when cancellation is allowed, and we terminate the process when cancellation is not allowed.
Problem SMPSC: In SMPSC, the knapsack capacity C is given according to some probability distribution. Let
Í
capacity is t. We
T = i ∈I s(i). For each t ∈ [T ] := {0, 1, . . . , T }, we denote by p(t) the probability that the knapsack
Í
assume that the probability is given to an algorithm through an oracle that returns the value of Tt′=t p(t ′) for any query
t ∈ [T ]. Hence, the input size of a problem instance is Θ(n log T ) and an algorithm runs in pseudo-polynomial time if
its running time depends on T linearly. A solution for SMPSC is a universal policy, i.e., a sequence Π = (Π1, . . . , Πn )
of the items in I. When a capacity C is decided, the output Π(C) of Π is constructed in the same way as universal
policies for SMPUC. The objective of SMPSC is to ﬁnd a sequence Π that maximizes EC [ f (Π(C))].

Multilinear extension, continuous greedy, and contention resolution scheme: From any vector x ∈ [0, 1]I , we
deﬁne a random subset Rx of I so that each i ∈ I is included in Rx with probability xi , where the inclusion of i is
independent from the inclusion of the other items.ÍFor a submodular
function
f : 2I → R+ , its multilinear extension
Î
Î
I
F : [0, 1] → R+ is deﬁned by F(x) = E[ f (Rx )] = X ⊆I f (X) i ∈X xi i′ ∈I \X (1− xi′ ) for all x ∈ [0, 1]I . This function
F satisﬁes the smooth monotone submodularity, that is, ∂F(x)/∂ xi ≥ 0 for any i ∈ I and ∂ 2 F(x)/(∂ xi ∂ x j ) ≤ 0 for
any i, j ∈ I. Although it is hard to compute the value of F(x) exactly, it usually can be approximated with arbitrary
precision by a Monte-Carlo simulation. In this paper, to make discussion simple, we assume that F can be computed
exactly.
A popular approach for solving the I-constrained submodular maximization problem is to use a continuous
relaxation of the problem. Let P ⊆ [0, 1]I be a polytope in which each integer vector in P is the incidence vector
of a member of I. Then, maxx ∈P F(x) ≥ maxX ∈I f (X) holds. In this approach, it is usually assumed that P is
downward-closed (i.e., if x, y ∈ [0, 1]I satisﬁes y ≤ x ∈ P, then y ∈ P), and solvable (i.e., the maximization problem
Í
maxx ∈P i ∈I wi xi can be solved in polynomial time for any w ∈ R+I ).
Calinescu et al. [3] gave an algorithm called continuous greedy for a continuous maximization problem maxx ∈P F(x)
over a solvable downward-closed polytope P. They proved that the continuous greedy outputs a vector x ∈ P such
that F(x) ≥ (1 − 1/e − o(1)) maxx′ ∈P F(x ′ ). Feldman [7] extended its analysis by observing that the continuous
greedy algorithm with stopping time b ≥ 0 outputs a vector x ∈ [0, 1]I such that x/b ∈ P and F(x) ≥ (1 − e−b −
o(1)) maxX ∈I f (X) (The performance guarantee depending on the stopping time is originally given for the measured
continuous greedy algorithm proposed by [8]). It is easy to see that his analysis can be modiﬁed to prove a slightly
stronger result F(x) ≥ (1 − e−b − o(1)) maxx′ ∈P F(x ′ ). In addition, this analysis requires only the smooth monotone
submodularity as a property of F.
A fractional vector x ∈ P can be rounded into an integer vector by a contention resolution scheme. Let b, c ∈ [0, 1].
For a vector x, we denote supp(x) = {i ∈ I : xi > 0}. We consider an algorithm that receives x ∈ {z : z/b ∈ P}
and A ⊆ I as inputs and returns a random subset π x (A) ⊆ A ∩ supp(x). Such an algorithm is called (b, c)-balanced
contention resolution scheme if π x (A) ∈ I with probability 1 for all x and A, and Pr[i ∈ π x (Rx ) | i ∈ Rx ] ≥ c holds
for all x and i ∈ supp(x) (recall that Rx is the random subset of I determined from x). It is also called monotone if
Pr[i ∈ π x (A)] ≥ Pr[i ∈ π x (A′)] for any i ∈ A ⊆ A′ ⊆ I. If a monotone (b, c)-balanced contention resolution scheme is
available, then we can achieve the approximation ratio claimed in the following theorem by applying it to a fractional
vector computed by the measured continuous greedy algorithm with stopping time b. This fact is summarized as in the
following theorem.

Theorem 1 ([8]). If there exists a monotone (b, c)-balanced contention resolution scheme for I, then the I-constrained
submodular maximization problem admits an approximation algorithm of ratio (1 − e−b )c − o(1) for any nonnegative
monotone submodular function.

3 Adaptive policies for SMPUC with cancellation
3.1 Randomized (1 − 1/e)/2-robust policy
In this subsection, we present a randomized adaptive policy for SMPUC in the situation that the cancellation is allowed.
The idea of our algorithm is based on a simple greedy algorithm [14] for the submodular maximization problem
with a knapsack constraint. The greedy algorithm generates two candidate item sets. One set is obtained greedily
by repeatedly inserting an item maximizing the increase in the objective function value per unit of size. The other is

5

Algorithm 1: Greedy algorithm P 1 for (I, U)
1
2
3
4
5
6
7
8
9

X ← U, R ← I \ U;
foreach j = 1, . . . , |I \ U| do
let i j ∈ arg max {( f (X ∪ {i}) − f (X))/s(i) : i ∈ R};
if i j fits the knapsack (i.e., s(X) + s(i j ) ≤ C) then // left subtree
X ← X ∪ {i j }
else // right subtree
discard i j
R ← R \ {i j };

return X;

Algorithm 2: Randomized (1 − 1/e)/2-robust adaptive policy
1
2
3
4
5
6
7
8
9
10
11
12

ﬂip a coin;
if head then execute Algorithm 1 for (I, ∅); // policy P 1
else // policy P 2
X ← ∅, R ← I;
foreach j = 1, . . . , |I | do
let i j ∈ arg max { f (X ∪ {i}) − f (X) : i ∈ R};
if i j fits the knapsack (i.e., s(X) + s(i j ) ≤ C) then // left subtree
X ← X ∪ {i j }
else // right subtree
discard i j
R ← R \ {i j };

return X;

obtained similarly by packing an item maximizing the increase in the objective function value. Then, the algorithm
returns the set with the larger value, which leads to a (1 − 1/e)/2-approximation solution.
The idea of choosing a better solution is not suitable for SMPUC, in which we cannot remove items from the
knapsack. We resolve this issue by generating at random one of two policies P 1 and P 2 that are analogous to the above
two greedy methods. One policy P 1 corresponds to the greedy algorithm based on the increase in the objective function
value per unit of size. We formally present this policy as Algorithm 1. The item i j corresponds to a node of depth
j − 1 in P 1 . We remark that Algorithm 1 chooses i j independently of the knapsack capacity, but the choice depends
on the observations which items ﬁt the knapsack and which items did not so far. For generality of the algorithm, we
assume that the algorithm receives an initial state U of the knapsack, which is deﬁned as a subset of I (this will be used
in Section 3.2).
The policy P 2 tries to pack items greedily based on the increase in the objective function value. Our algorithm is
summarized in Algorithm 2. We remark that Algorithm 2 chooses the item i j for each iteration j in polynomial time
with respect to the cardinality of I.
We analyze the robustness ratio of Algorithm 2. In the execution of Algorithm 1 for (I, U) under some capacity
C, we call the order (i1, . . . , i |I \U | ) of items in I \ U the greedy order for (I, U) with capacity C, where i j is the jth
selected item at line 3. A key concept in the analysis of Algorithm 2 is to focus on the ﬁrst item in the greedy order
that is a member of OPTC but is spilled from P 1 (C). The following lemma is useful in analysis of Algorithm 2 and
also algorithms given in subsequent sections.
Lemma 1. Let C, C ′ be any positive numbers, and let q be the smallest index such that iq ∈ OPTC ′ and iq < P 1 (C) (let
q = ∞ if there is no such index). When Algorithm 1 is executed for (I, U) with capacity C, it holds for any index j that
!!
s((P 1 (C) ∪ OPTC ′ ) ∩ {i1, . . . , i j })
1
· f (OPTC ′ ).
f (((P (C) ∪ OPTC ′ ) ∩ {i1, . . . , i j }) ∪ U) ≥ 1 − exp −
C′
6

Moreover, (P 1 (C) ∪ OPTC ′ ) ∩ {i1, . . . , i j } = P 1 (C) ∩ {i1, . . . , i j } holds for any j < q.
To prove Lemma 1, we show the following two lemmas.
Lemma 2. For any X ⊆ Y ⊆ I, we have
f (Y) ≤ f (X) +

Õ

i ∈Y \X

( f (X ∪ {i}) − f (X)).

Proof. Suppose that Y \ X = {a1, . . . , al }, where l = |Y \ X |. Let X j = X ∪ {a1, . . . , a j } for each j = 1, . . . , l. Note that
X0 = X and Xl = Y . Since f is submodular, we have f (X j ) − f (X j−1 ) ≤ f (X ∪ {a j }) − f (X). By summing both sides
Í
Í
over j, we obtain f (Y) − f (X) = lj=1 ( f (X j ) − f (X j−1 )) ≤ lj=1 ( f (X ∪ {a j }) − f (X)), which proves the lemma. 
Lemma 3. Let C be any positive number. For any X ⊆ Y ⊆ I and any i ∈ I \ Y such that OPTC \ X ⊆ I \ Y and


f (X ∪ {i}) − f (X)
f (X ∪ {v}) − f (X)
= max
: v ∈ I \Y ,
s(i)
s(v)

it holds that
s(i)
( f (OPTC ) − f (X)).
C
Í
Proof. By applying Lemma 2 with Y = OPTC ∪ X (⊇ X), we have f (OPTC ∪ X) ≤ f (X) + v ∈OPTC \X ( f (X ∪ {v}) −
f (X)). In addition, f (OPTC ) ≤ f (OPTC ∪ X) holds by monotonicity. Thus, we have
Õ
Õ
f (X ∪ {v}) − f (X)
f (OPTC ) − f (X) ≤
( f (X ∪ {v}) − f (X)) =
s(v) ·
s(v)
f (X ∪ {i}) − f (X) ≥

v ∈OPTC \X

v ∈OPTC \X

f (X ∪ {i}) − f (X)
© Õ
ª f (X ∪ {i}) − f (X)
s(v)® ·
≤­
≤C·
.
s(i)
s(i)
¬
«v ∈OPTC \X



Proof of Lemma 1. We denote Yj = U ∪ {i1, . . . , i j } and Z j = (P 1 (C) ∪ OPTC ′ ) ∩ {i1, . . . , i j } for each j. Let Y0 = U
and Z0 = ∅. We ﬁrst prove by induction on j that f (Z j ∪ U) ≥ (1 − exp(−s(Z j )/C ′ )) · f (OPTC ′ ) for any j. For j = 0,
the statement clearly holds because 1 − exp(−s(Z0 )/C ′) = 0 and f (Z0 ∪ U) ≥ f (∅) = 0.
Suppose that f (Z j−1 ∪ U) ≥ (1 − exp(−s(Z j−1 )/C ′)) · f (OPTC ′ ) holds for some j ≥ 0. If i j < P 1 (C) ∪ OPTC ′ , then
we have Z j = Z j−1 , and hence it is easy to see that f (Z j ∪ U) ≥ (1 − exp(−s(Z j )/C ′ )) · f (OPTC ′ ). In the following,
we may assume that i j ∈ P 1 (C) ∪ OPTC ′ . Note that Z j−1 ∪ {i j } = Z j . We observe that by choice of i j in Algorithm 1,
it holds that


f ((Z j−1 ∪ U) ∪ {v}) − f (Z j−1 ∪ U)
f ((Z j−1 ∪ U) ∪ {i j }) − f (Z j−1 ∪ U)
= max
: v ∈ I \ Yj−1 .
s(i j )
s(v)
Because OPTC ′ \ (Z j−1 ∪ U) ⊆ I \ Yj−1 , we can apply Lemma 3 with X = Z j−1 ∪ U, Y = Yj−1 and i = i j to derive
f (Z j ∪ U) − f (Z j−1 ∪ U) ≥

s(i j )
( f (OPTC ′ ) − f (Z j−1 ∪ U)).
C′

Therefore, by using this inequality, we see that
s(i j )
f (Z j ∪ U) ≥ f (Z j−1 ∪ U) + ′ ( f (OPTC ′ ) − f (Z j−1 ∪ U))
C


s(i j )
s(i j )
= 1 − ′ f (Z j−1 ∪ U) + ′ f (OPTC ′ )
C
C

 


s(i j )
s(Z j−1 )
s(i j )
≥ 1 − ′ · 1 − exp −
· f (OPTC ′ ) + ′ f (OPTC ′ )
′
C
C
C





s(Z j−1 )
s(i j )
· f (OPTC ′ )
= 1 − 1 − ′ · exp −
C
C′








s(Z j−1 )
s(Z j )
s(i j )
′ ) = 1 − exp −
·
f
(OPT
· f (OPTC ′ ),
≥ 1 − exp − ′ · exp −
C
C
C′
C′
7

where the last inequality holds because 1 − x ≤ exp(−x) for any x.
It remains to show that Z j = P 1 (C) ∩ {i1, . . . , i j } for any j < q. The inclusion ⊇ is clear. For any j ≤ q, we have
OPTC ′ ∩ {i1, . . . , i j } ⊆ P 1 (C) ∩ {i1, . . . , i j } by choice of q. Thus, Z j = (OPTC ′ ∩ {i1, . . . , i j }) ∪ (P 1 (C) ∩ {i1, . . . , i j }) ⊆
P 1 (C) ∩ {i1, . . . , i j }. This completes the proof.

We are ready to analyze the robustness ratio of Algorithm 2. For any C ∈ R+ , we denote IC = {i : s(i) ≤ C} and
denote by iC an item with the largest value in this set, i.e., iC ∈ arg max{ f ({i}) : i ∈ IC }.
Theorem 2. Algorithm 2 is a randomized (1 − 1/e)/2 > 0.316-robust adaptive policy.
Proof. Let P 1 (respectively, P 2 ) be the adaptive policy in Algorithm 2 when the coin comes up head (respectively,
tail). Suppose that the given capacity is C. The expected value of the output by Algorithm 2 is ALGC = ( f (P 1 (C)) +
f (P 2 (C)))/2. If OPTC ⊆ P 1 (C), then we get ALGC ≥ f (P 1 (C))/2 ≥ f (OPTC )/2. Assume that OPTC * P 1 (C).
Let (i1, i2, . . . , in ) be the greedy order for (I, ∅) with capacity C. Let q be the smallest index such that iq ∈ OPTC and
iq < P 1 (C). We have f (P 2 (C)) ≥ f ({iC }) ≥ f ({iq }) because iC ∈ P 2 (C) and iq ∈ IC . By the monotonicity and
submodularity of f , we have
ALGC ≥

f (P 1 (C) ∩ {i1, . . . , iq−1 }) + f ({iq })
f ((P 1(C) ∩ {i1, . . . , iq−1 }) ∪ {iq })
≥
.
2
2

Note that by the choice of q, we have (P 1 (C) ∩ {i1, . . . , iq−1 }) ∪ {iq } = (P 1 (C) ∪ OPTC ) ∩ {i1, . . . , iq } and s((P 1 (C) ∩
{i1, . . . , iq−1 }) ∪ {iq }) > C. Thus, Lemma 1 implies that f ((P 1 (C) ∪ OPTC ) ∩ {i1, . . . , iq }) ≥ (1 − 1/e) f (OPTC ), and
hence we have ALGC ≥ (1 − 1/e) f (OPTC )/2.


3.2 Deterministic 2(1 − 1/e)/21-robust policy
In this subsection, we present a deterministic adaptive policy for SMPUC by modifying Algorithm 2. To this end, let
us review the result of Disser et al. [6] for KPUC, which is identical to SMPUC with modular objective functions.
They obtained a deterministic 1/2-robust universal policy for KPUC based on the greedy order for (I, ∅) with the given
capacity. Their policy ﬁrst tries to insert items with large values, which are called swap items. For a greedy order
(i1, . . . , in ), an item i j is called a swap item if f ({i j }) ≥ f (P 1 (C)) for some capacity C such that i j is the ﬁrst item that
overﬂows the knapsack when the items are packed in the greedy order. The key property is that the greedy order does
not depend on the capacity C when f is modular. This enables them to determine swap items from the unique greedy
order, and to obtain a deterministic universal policy.
On the other hand, it is hard to apply their idea to our purpose. The diﬃculty is that the greedy order varies
according to the capacity when f is submodular. Thus, the notion of swap items is not suitable in SMPUC for choosing
the items that should be tried ﬁrst. In this paper, we introduce single-valuable items, which are items i satisfying
f ({i}) ≥ 2 · f (OPTs(i)/2 ) (= 2 · max{ f (X) : s(X) ≤ s(i)/2}). In the design of our algorithm, we use a polynomial-time
γ-approximation algorithm that computes f (OPTs(i)/2 ); for example, γ = 1 − 1/e [18]. Our algorithm calculates the
set S of the single-valuable items in a sense of γ-approximation. To be precise, it holds that f ({i}) ≥ 2γ · f (OPTs(i)/2 )
for any item i ∈ S and f ({i}) ≤ 2 · f (OPTs(i)/2 ) for any item i < S.
Our algorithm ﬁrst tries to insert items in S until one of these items ﬁts the knapsack (or all the items have
been canceled) and then it executes Algorithm 1 with the remaining items. We remark that, unlike the algorithm for
KPUC [6], our algorithm executes Algorithm 1 once a single-valuable item ﬁts the knapsack. We summarize our
algorithm in Algorithm 3.
Note that our algorithm constructs S and decides which item to try in polynomial time. In the rest of this subsection,
we let R, U, and S denote the item sets at the beginning of line 10. Then U is empty if S ∩ IC = ∅, and U consists of
exactly one item i ∗ ∈ arg max{ f ({i}) : i ∈ IC ∩ S} otherwise. The following theorem is the main result of this section.
√
e)/3}-robust universal
Theorem 3. Algorithm 3 using a γ-approximation algorithm in line 3 is a min{2γ/21, (1 − 1/ 3 √
policy. In particular, it is 2(1 − 1/e)/21 > 0.060-robust when γ = 1 − 1/e, and it is (1 − 1/ 3 e)/3 > 0.094-robust
when γ = 1.
We describe the proof idea. We discuss the behavior of Algorithm 3 when the given capacity is C. Since the output
of Algorithm 3 is P 1 (C) for (R ∪ U, U), one can think of a similar proof to the one of Theorem 2. However, we may
not be able to use the value f ({iq }) in the evaluation of f (P 1 (C)) here because P 1 (C) may not contain any items that
8

Algorithm 3: Deterministic 2γ/21-robust policy
1
2
3
4
5
6
7
8
9
10

U ← ∅, R ← I, S ← ∅;
foreach i ∈ I do
Let L be a γ-approximate solution to max{ f (X) : s(X) ≤ s(i)/2, X ⊆ I };
if f ({i}) ≥ 2 f (L) then S ← S ∪ {i};
while U = ∅ and S ∩ R , ∅ do
let i ∈ arg max{ f ({i}) : i ∈ S ∩ R};
if i fits the knapsack (i.e., s(i) ≤ C) then U ← {i}; // left subtree
else discard i; // right subtree
R ← R \ {i};

execute Algorithm 1 for (R ∪ U, U);

bound f ({iq }). We show the theorem using a diﬀerent approach. A basic idea is to divide OPTC into several subsets
A1, . . . , Ak and derive a bound f (OPTC ) ≤ f (A1 ) + · · · + f (Ak ) by the submodularity of f . A key idea is to evaluate
each f (Ai ) using properties of single-valuable items, which are shown as the following two lemmas.
Lemma 4. It holds that f ({i}) ≤ max{ f (U), 2 f (OPTs(i)/2 )} for any item i ∈ IC .
Proof. The lemma follows because f ({i}) ≤ f (U) if i ∈ S and f ({i}) ≤ 2 f (OPTs(i)/2 ) if i < S.



Lemma 5. Let s∗ = s(U). If s∗ ≤ C/2, then, for any number x ∈ [s∗, C/2], it holds that f (OPT2x ) ≤ 3 f (OPTx ).
Proof. First, suppose that OPT2x contains some item i with s(i) > x and i ∈ S. Then we have f (OPT2x ) ≤
f ({i}) + f (OPT2x \ {i}) by the submodularity of f . Since the existence of item i implies IC ∩ S , ∅, U consists
of exactly one item from S. We denote this item by i ∗ . Any item i ′ ∈ S with f ({i ′ }) > f ({i ∗ }) does not ﬁt the
knapsack with capacity C ≥ 2x. This implies that f ({i}) ≤ f ({i ∗ }). Moreover, we have f ({i ∗ }) ≤ f (OPTx ) because
s(i ∗ ) = s∗ ≤ x. Hence, f ({i}) ≤ f (OPTx ) follows. On the other hand, f (OPT2x \ {i}) ≤ f (OPT2x−s(i) ) ≤ f (OPTx )
holds, where the last inequality follows from s(i) > x. Therefore, we see that
f (OPT2x ) ≤ f ({i}) + f (OPT2x \ {i}) ≤ 2 f (OPTx ).
Second, suppose that OPT2x contains some item i with s(i) > x and i < S. Recall that i < S implies f ({i}) ≤
2 f (OPTs(i)/2 ). Since s(i)/2 ≤ x < s(i), we see that
f (OPT2x ) ≤ f ({i}) + f (OPT2x \ {i}) ≤ 2 f (OPTs(i)/2 ) + f (OPT2x−s(i) ) ≤ 3 f (OPTx ).
Finally, assume that all items in OPT2x have size at most x. We can divide OPT2x into three sets A1, A2, A3 with
s(A j ) ≤ x ( j = 1, 2, 3). Therefore, we have
f (OPT2x ) ≤ f (A1 ) + f (A2 ) + f (A3 ) ≤ 3 f (OPTx ).
The lemma follows from the arguments on the three cases.



Proof of Theorem 3. Let P be the deterministic policy described as Algorithm 3. Suppose that the given capacity is
C. We remark that P(C) = P 1 (C) for (R ∪ U, U). We may assume that OPTC * P(C) since otherwise f (P(C)) =
f (OPTC ). Let s∗ = s(U). We branch the analysis into two cases: (a) s∗ < C/3 and (b) s∗ ≥ C/3.
Case (a): We claim that
√
f (P(C)) ≥ (1 − 1/ 3 e) · f (OPTC )/3.
Since s∗ < C/3 < C/2, Lemma 5 indicates that f (OPTC/2 ) ≥ f (OPTC )/3. We evaluate f (OPTC/2 ) by using Lemma
1 with C ′ = C/2. We may assume that OPTC/2 * P(C); otherwise f (P(C)) ≥ f (OPTC/2 ) holds, which implies that
f (P(C)) ≥ f (OPTC )/3. Let (i1, . . . , i |R | ) be the greedy order for (R ∪ U, U) with capacity C. Let q ′ be the smallest

9

index such that iq′ ∈ OPTC/2 and iq′ < P 1 (C). We denote Z = P 1 (C) ∩ {i1, . . . , iq′ −1 }. As s(iq′ ) ≤ C/2, we see that
s(Z) > C − s∗ − s(iq′ ) ≥ C/6. Then Lemma 1 implies that
√
f (P(C)) ≥ f (Z ∪ U) ≥ (1 − 1/ 3 e) · f (OPTC/2 ),

and hence the claim follows.
Case (b): In this case, we prove the following two claims. Note that U is nonempty since s∗ > 0. Let i ∗ denote the
unique item in U.
Claim 1. f (OPTC ) ≤ 7 f (OPTs∗ ).
Proof. Let T ′ = {i ∈ OPTC : s(i) > s∗ }. Since C ≤ 3s∗ , we observe that T ′ has at most two items. We evaluate
f (OPTC ) by splitting OPTC depending on T ′.
Suppose that T ′ = {i} and 2s∗ ≤ s(i) (≤ C). It follows that f (OPTC ) ≤ f ({i}) + f (OPTC \ {i}). By Lemma
4, we have f ({i}) ≤ max{ f (U), 2 f (OPTs(i)/2 )} ≤ max{ f (OPTs∗ ), 2 f (OPTs(i)/2 )}. Since s(i)/2 ≤ C/2 < 2s∗ , it
follows that max{ f (OPTs∗ ), 2 f (OPTs(i)/2 )} ≤ 2 f (OPT2s∗ ), which is at most 6 f (OPTs∗ ) by Lemma 5 together with
s∗ ≤ s(i)/2 ≤ C/2. Moreover, we have f (OPTC \ {i}) ≤ f (OPTC−s(i) ) ≤ f (OPTs∗ ) since C − s(i) ≤ 3s∗ − 2s∗ = s∗ .
Thus, we obtain
f (OPTC ) ≤ f ({i}) + f (OPTC \ {i}) ≤ 6 f (OPTs∗ ) + f (OPTs∗ ) = 7 f (OPTs∗ ).
Assume that T ′ = {i} and s(i) < 2s∗ . We observe that f ({i}) ≤ 2 f (OPTs∗ ) by Lemma 4 and s(i)/2 < s∗ . Note
that all items in OPTC \ {i} have size at most s∗ and their total size is at most 2s∗ . Thus we can divide OPTC \ {i} into
three sets A1, A2, A3 with s(A j ) ≤ s∗ ( j = 1, 2, 3). Hence, we have
f (OPTC ) ≤ f ({i}) + f (OPTC \ {i}) ≤ 2 f (OPTs∗ ) + 3 f (OPTs∗ ) = 5 f (OPTs∗ ).
If T ′ = {i, i ′ }, then s(i), s(i ′ ) < 2s∗ and C − s(i) − s(i ′ ) < s∗ . In this case, by Lemma 4 and s(i)/2, s(i ′ )/2 < s∗ , we
have f ({i}), f ({i ′ }) ≤ 2 f (OPTs∗ ). This implies that
f (OPTC ) ≤ f ({i}) + f ({i ′ }) + f (OPTC \ {i, i ′ }) ≤ (2 + 2 + 1) f (OPTs∗ ) = 5 f (OPTs∗ ).
Finally, if T ′ = ∅, i.e., s(i) ≤ s∗ for all i ∈ OPTC , then we can divide OPTC into ﬁve sets A1, . . . , A5 with
s(A j ) ≤ s∗ (∀ j), and hence we have f (OPTC ) ≤ f (A1 ) + · · · + f (A5 ) ≤ 5 f (OPTs∗ ). Therefore, the claim holds.

Claim 2. f (OPTs∗ ) ≤

3
2γ

· f ({i ∗ }).

Proof. Recall that f ({i ∗ }) ≥ 2γ · f (OPTs∗ /2 ). Take an arbitrary item i with the largest size in OPTs∗ .
Assume that s(i) > s∗ /2 and i ∈ S. We have f ({i}) ≤ max{ f ({i ′ }) : i ′ ∈ IC ∩ S} = f ({i ∗ }) since i ∈ S and
∗
s(i) ≤ s∗ ≤ C. Moreover, f (OPTs∗ \ {i}) ≤ f (OPTs∗ −s(i) ) ≤ f (OPT
s ∗ /2) follows from s(i) > s /2. Hence, we have

1
f (OPTs∗ ) ≤ f ({i}) + f (OPTs∗ \ {i}) ≤ f ({i ∗ }) + f (OPTs∗ /2 ) ≤ 1 + 2γ
f ({i ∗ }).
Suppose that s(i) > s∗ /2 and i < S. Then, f ({i}) ≤ 2 f (OPTs(i)/2 ) ≤ 2 f (OPTs∗ /2 ) holds by i < S and s(i) ≤ s∗ ,
and f (OPTs∗ \ {i}) ≤ f (OPTs∗ /2 ) holds by s(i) > s∗ /2. These imply that f (OPTs∗ ) ≤ f ({i}) + f (OPTs∗ \ {i}) ≤
3
2 f (OPTs∗ /2 ) + f (OPTs∗ /2 ) ≤ 2γ
f ({i ∗ }).
∗
If s(i) ≤ s /2, then we can divide OPTs∗ \ {i} into two sets A1, A2 such that s(A j ) ≤ s∗ /2 ( j = 1, 2), and hence it
3
· f ({i ∗ }). Therefore, the claim
follows that f (OPTs∗ ) ≤ f (OPTs(A1 ) ) + f (OPTs(A2 ) ) + f (OPTs(i) ) ≤ 3 f (OPTs∗ /2 ) ≤ 2γ
follows since 3/(2γ) ≥ 1 + 1/(2γ).


Combining these claims give f (P(C)) ≥ (2γ/21) · f (OPTC ). Hence the theorem is proven.

10



√
Algorithm 4: Randomized (1 − 1/ 4 e)/2-robust universal policy
1
2
3
4
5
6
7
8
9

Π ← ();
ﬂip a coin;
if head then
l ← 1, smin ← mini ∈I s(i);
Í
for k ← 0 to ⌈log2 ( i ∈I s(i)/smin )⌉ do
let Y (k) be the output P 1 (2k · smin ) of the policy given in Algorithm 1 for (I, ∅);
Ð
(j) do Π ← i, l ← l + 1;
foreach i ∈ Y (k) \ k−1
l
j=0 Y

else let Π be the decreasing order of items i ∈ I in value f ({i}) ;
return Π;

√
3.3 Randomized (1 − 1/ 4 e)/2-robust universal policy

√
In this subsection, we devise a randomized (1 − 1/ 4 e)/2-robust universal policy by modifying Algorithm 2. Note that
we cannot use directly Algorithm 1 in universal policies, because they do not use the observation while packing items
so far. Instead we guess the capacity by the doubling strategy and emulate the execution of Algorithm 1. Our algorithm
iteratively ﬁnds an item set X maximizing f (X) under a bound C ′ on the total size s(X), and then appends items of
X to the sequence. The bound C ′ is set by the algorithm according to the input items. To compute the set X, we use
Algorithm 1 in which the capacity is set to be C ′. We double the bound after each iteration.
Also, we cannot use the other adaptive policy P 2 in Algorithm 2. We remark that the proof of Theorem 2 uses
only the fact that f (P 2 (C)) contains iC regarding to the policy P 2 . This implies that in the worst case analysis, there
is no diﬀerence between P 2 and a universal policy that inserts items based on the decreasing order according to the
values of f . Thus, we replace P 2 with the universal policy. Our algorithm is summarized in Algorithm 4.
We remark that Algorithm 4 constructs a sequence of items in polynomial time with respect to the input size. We
can prove the following result by using Lemma 1.
√
Theorem 4. Algorithm 4 is a (1 − 1/ 4 e)/2 > 0.110-robust randomized universal policy.
Proof. Let Π 1 (respectively, Π 2 ) be the sequence of items in I returned by Algorithm 4 when the coin comes up
head (respectively, tail). Suppose that the given capacity is C. The expected value of the output of Algorithm 4 is
f (ALGC ) = ( f (Π 1 (C)) + f (Π 2 (C)))/2. We assume that C ≥ smin since otherwise f (OPTC ) = ALGC = 0. Recall that
smin = mini ∈I s(i). Let k be the number satisfying 2k−1 · smin ≤ C < 2k · smin . We let iC ∈ arg max{ f ({i}) : s(i) ≤ C}.
When k = 1 (i.e., C < 2smin ), we have OPTC = {iC } because we can put only one item into the knapsack in this case.
We also have Π 2 (C) = {iC }. Hence, it holds that f (OPTC ) = f (Π 2 (C)) ≤ 2 · ( f (Π 1 (C)) + f (Π 2 (C)))/2 = 2 · f (ALGC ).
Ð
(j) is at most s Ðk−2 Y (j) ≤
In what follows, we assume k ≥ 2. We observe that the total size of items in k−2
j=0 Y
j=0
Ík−2
Ík−2 j
Ðk−2 (j)
(j)
k−1
· smin ≤ C. Thus, all items in j=0 Y , in particular those in Y (k−2) , are
j=0 s(Y ) ≤
j=0 2 · smin ≤ 2
1
contained in Π (C). We also observe that f (Π 2 (C)) ≥ f ({iC }) because iC ∈ Π 2 (C). Hence, it holds that 2 f (ALGC ) =
f (Π 1 (C)) + f (Π 2 (C)) ≥ f (Y (k−2) ) + f ({iC }).
We denote C ′ = 2k−2 · smin . Recall that Y (k−2) is the output of the greedy algorithm for (I, ∅) when the capacity is
′
C . Let (i1, i2, . . . , in ) be the greedy order for (I, ∅) with capacity C ′ . Let q be the smallest index such that iq ∈ OPTC
and iq < Y (k−2) . Since this deﬁnition implies iq ∈ IC , we have f ({iC }) ≥ f ({iq }). By the monotonicity of f , we also
have f (Y (k−2) ) ≥ f (Y (k−2) ∩ {i1, . . . , iq−1 }). Hence,
f (ALGC ) ≥

f ((Y (k−2) ∩ {i1, . . . , iq−1 }) ∪ {iq })
f (Y (k−2) ∩ {i1, . . . , iq−1 }) + f ({iq })
≥
.
2
2

We evaluate f ((Y (k−2) ∩ {i1, . . . , iq−1 }) ∪ {iq }) using Lemma 1. For notational convenience, we denote Y ′ = (Y (k−2) ∪
OPTC ) ∩ {i1, . . . , iq }. In a similar way to the proof of Theorem 2, we can see that (Y (k−2) ∩ {i1, . . . , iq−1 }) ∪ {iq } = Y ′
′
′
k−2 · s
k
by the choice of q. Thus, we have s(Y ′ ) > C ′ , and it follows that√s(Y
min )/(2 · smin ) = 1/4.
 )/C ≥ C /C ≥ (2
Therefore, by Lemma 1, we have f (ALGC ) ≥ f (Y ′ )/2 ≥ 1 − 1/ 4 e f (OPTC )/2.


11

4 Upper bounds on robustness ratios
4.1 Randomized policies for KPUC with cancellation
In this subsection, we prove that no randomized policy achieves a robustness ratio better than 8/9 even if the objective
function is modular when cancellation is allowed. It is known that the robustness ratio achieved by any deterministic
policies for KPUC is at most 1/2 [6], but there was no upper bound on the robustness ratio for randomized policies.
Suppose that there are three items a, b, c whose sizes are 2, 3, 4, respectively, and whose weights are equal to their
own sizes. Recall that the objective value is deﬁned as the sum of the weights of selected items. Let OPTC ′ be an
optimal solution when the capacity is C ′ ∈ R+ . We provide an upper bound for this instance using Yao’s principle
[19]. We consider an adversary that submits a probability distribution for the capacity as a mixed strategy. Let C be
the random variable which represents the capacity. Then, the robustness ratio for this instance is upper-bounded by


f (P(C ′))
f (P(C))
max min
,
≤ max EC
P C ′ ∈R+ f (OPTC ′ )
P
f (OPTC )
where the maximum is taken over all randomized policies P.
We assume that the adversary submits C = 4 with probability 4/9 and C = 5 with probability 5/9. Then, we have




4 f (P(4)) 5 f (P(5))
f (P(C))
= max
.
·
+ ·
max EC
P
P
f (OPTC )
9 f (OPT4 ) 9 f (OPT5 )
Note that f (OPT4 ) = 4 and f (OPT4 ) = 5. Hence the right-hand side is equal to max P ( f (P(4)) + f (P(5)))/9. In
what follows, we prove that this is at most 8/9. Note that the maximum is attained by a deterministic policy. If a
deterministic policy P chooses item a ﬁrst, then it can get objective value 2 when the capacity is 4. Thus, we have
f (P(4)) + f (P(5)) ≤ 2 + 5 = 7. Similarly, the value is at most 3 + 5 = 8 if it selects b ﬁrst and the value is at most
4 + 4 = 8 if it selects c ﬁrst. Since f (P(4)) + f (P(5)) ≤ max{7, 8, 8} = 8, we obtain the following theorem.
Theorem 5. Even if cancellation is allowed, no randomized policy has a robustness ratio better than 8/9 > 0.888 for
KPUC.

4.2 Randomized policies for KPUC without cancellation
In this subsection, we prove that no randomized policy achieves a constant robustness ratio for KPUC in the setting
where cancellation is not allowed.
Let M be a positive integer of at least 2. We assume that the item set I Í
consists of n items 1, . . . , n, and the size and
the weight of item i is M i . The objective function f is deﬁned by f (S) = i ∈S M i for any S ⊆ I. We ﬁx a policy, and
show that the robustness ratio of this policy is O(1/M) for this instance if n = Ω(M).
Since there are n items, at least one item is chosen ﬁrst by the policy with probability at most 1/n. Let i denote such
an item. Let us consider the case where the capacity is M i . When the policy does not choose i ﬁrst (this happens with
Í
i′
i−1 . Therefore,
probability at least (n − 1)/n), the largest objective value achieved by the solution is i−1
i′ =1 M ≤ 2M
i
i−1
the expected objective value of the policy is at most M /n + (n − 1)/n · 2M . On the other hand, the optimal solution
for this instance consists of only item i, which attains the objective value M i . The gap between these values is O(1/M)
if n = Ω(M).
Theorem 6. If cancellation is not allowed, then no randomized policy achieves a constant robustness ratio for KPUC.

4.3 Deterministic policies for the unit size case of SMPUC
In this subsection, we consider a special case of SMPUC in which the size of each item is 1, i.e., the cardinality constraint
case. We show√that no deterministic policy (even one with no computational restrictions) achieves a√robustness ratio
better than (1 + 5)/4 (> 0.809), and no randomized policy achieves a robustness ratio better than (5 + 5)/8 (> 0.904)
for this case. We remark that the cancellation is not useful in the cardinality constraint case. Also, for the cardinality
constraint case of SMPUC, a greedy algorithm achieves (1 − 1/e)-robust (-approximation) and it is known to be the
best possible among policies that run in polynomial time.

12

To present the upper bound on the robustness ratio, let us construct an instance of the problem. Suppose that there
are three items a, b, c, each of whose size is 1, and the objective function f is given by
√
f (∅) = 0, f ({a}) = 4, f ({b}) = f ({c}) = 1 + 5,
√
√
f ({a, b}) = f ({a, c}) = 3 + 5, f ({b, c}) = f ({a, b, c}) = 2 + 2 5.
Note that the function is monotone submodular and symmetric in b and c. If the policy ﬁrst packs a, then the
robustness
ratio√for capacity
√
√ 1 is equal to f ({a}/ f ({a}) = 1, and the one for capacity 2 is f ({a, b})/ f ({b, c}) =
(3 + 5)/(2 + 2 √5) = (1 + 5)/4. Otherwise, i.e., the policy ﬁrst packs b or c, then the √
robustness ratio for capacity 1
})
is ff ({b
=
(1
+
5)/4,
and
the
one
for
capacity
2
is
at
least
f
({a,
b})/
f
({b,
c})
=
(1
+
5)/4. Thus, no deterministic
({a })
√
policy achieves a robustness ratio better than (1 + 5)/4.
√
Finally, we prove that no randomized policy achieves a robustness ratio better than (5 + 5)/8. Let us consider a
randomized policy for the above instance that ﬁrst inserts a with probability p. Then the robustness ratio for capacity
1 is
√
√
√
p · f ({a}) + (1 − p) · f ({b}) 4p + (1 − p)(1 + 5) (3 − 5)p + (1 + 5)
=
=
.
f ({a})
4
4
Also, the robustness ratio for capacity 2 is at most
√
√
√
p · f ({a, b}) + (1 − p) · f ({b, c}) (3 + 5)p + (2 + 2 5)(1 − p) 4 − (3 − 5)p
=
.
=
√
f ({b, c})
4
(2 + 2 5)
Note that the former value is monotone increasing for p, and the latter is monotone decreasing for p. Thus, the
robustness ratio of the policy is at most
)
(
√
√
√
√
5+ 5
(3 − 5)p + (1 + 5) 4 − (3 − 5)p
≤
,
,
min
4
4
8
where the inequality holds when p = 1/2.
Theorem
7. For SMPUC with only unit-size items, no deterministic policy achieves
√ a robustness ratio better than
√
(1 + 5)/4, and no randomized policy achieves a robustness ratio better than (5 + 5)/8.

5 Approximation algorithms for SMPSC without cancellation
5.1 Pseudo-polynomial time (1/4 − o(1))-approximation algorithm
We present a pseudo-polynomial time (1/4 − o(1))-approximation algorithm for SMPSC without cancellation. We
reduce the problem to the following problem.
Submodular maximization problem with an interval independent constraint: We are given a set I of items. Each
item i ∈ I is associated with an interval li on a line. We are also given a submodular function f : 2I → R+ . The
objective is to ﬁnd a subset I ′ of I maximizing f (I ′) subject to the constraint that no two intervals associated with
items in I ′ intersect, i.e., li ∩ l j = ∅ for all i, j ∈ I ′ .
Feldman [7] showed that this problem admits a (1/4 − o(1))-approximation randomized algorithm for monotone
submodular functions.
Let us explain the reduction from SMPSC to this problem. Let I be the set of items and f : 2I → R+ be the
submodular function given in an instance of SMPSC. Recall that T = s(I) and [T ′] = {0, 1, . . . , T ′ }. For each i ∈ I, we
make T − s(i) + 1 copy items i0, . . . , iT −s(i) , and i j is associated with the interval [ j, j + si − 1] for each j ∈ [T − si ].
′
Let I ′ denote the set of these items. We deﬁne a function f ′ : 2I → R+ by
f ′(U ′ ) =

T
Õ
t=0

p(t) f ({i ∈ I : ∃ j ∈ [t − si ], i j ∈ U ′ })

for all U ′ ⊆ I ′ . It is not diﬃcult to prove the following lemma.
13

Lemma 6. The function f ′ is monotone and submodular.
Let U ′ ⊆ I ′ be a solution for the instance of the problem with an interval independent constraint that consists of
the item set I ′ (with associated intervals) and the submodular function f ′ . From U ′, we deﬁne the ordering of I as
follows. If a copy of i ∈ I is included in U ′, then pick item i at the time equal to the minimum index of its copies in U ′,
i.e, min{t ∈ [T ] : it ∈ U ′ }. Sort the items in the increasing order of the times at which they are picked. The other items
follow these items, and their order is decided arbitrarily. This sequence achieves the objective value of at least f ′(U ′ ).
Theorem 8. Problem SMPSC without cancellation admits a pseudo-polynomial time randomized (1/4 − o(1))approximation algorithm for monotone submodular functions.
Feldman [7] also gave a randomized 1/(2e + o(1))-approximation algorithm for the problem with an interval
independent constraint and nonmonotone submodular functions. Thus, if the submodular function is not monotone,
then SMPSC admits a pseudo-polynomial time randomized 1/(2e + o(1))-approximation algorithm.

√
5.2 Polynomial-time ((1 − 1/ 4 e)/4 − ǫ)-approximation algorithm

√
In this subsection, we present a polynomial-time algorithm of approximation ratio (1 − 1/ 4 e)/4 − ǫ for any small
constant ǫ > 0. This algorithm is based on√the idea of Gupta et al. [11] for the stochastic knapsack problem. We
ﬁrst give a pseudo-polynomial time ((1 − 1/ 4 e)/2 − o(1))-approximation algorithm, and then we transform it into a
polynomial-time algorithm.
Our algorithm relies on a continuous relaxation of the problem. The relaxation is formulated based on an idea
of using time-indexed variables; we regard the knapsack capacity as a time limit while considering that picking an
item i spends time s(i). In the relaxation, we have a variable xti ∈ [0, 1] for each t ∈ [T − 1] and i ∈ I, and xti = 1
Í
represents that item i is picked at time t. For each t ∈ [T ] and i ∈ I, let x̄ti = t ′ ∈[t−s(i)] xt ′i if t ≥ s(i), and let x̄ti = 0
otherwise. For each t ∈ [T ], let x̄t be the |I |-dimensional vector whose component corresponding to i ∈ I is x̄ti . Let
F : [0, 1]I → R+ be the multilinear extension of the submodular function f . Then, the relaxation is described as
Í
maximize F̄(x) := Tt=1 p(t)F( x̄t )
Í
∀i ∈ I,
subject to
−1] xti ≤ 1,
Ít ∈[TÍ
(1)
′
x
min{s(i),
t}
≤
2t,
∀t = 1, . . . , T,
′
i ∈I
t ∈[t] t i
xti ≥ 0,
∀t ∈ [T − 1], ∀i ∈ I.
Let us see that (1) relaxes the problem. It is not diﬃcult to see that the ﬁrst and the third constants are valid. We prove
′
that the second constraint is valid. Suppose that x is an integer solutionÍthat Í
corresponds to a sequence
Íof items. Let I
be the set of items picked at time t or earlier in this solution. Notice that i ∈I t ′ ∈[t] xt ′ i min{s(i), t} = i ∈I ′ min{s(i), t}
holds. Let j be the item picked latest in I ′. Then, since the process of all items in I ′ \ { j} terminates by time t, we
Í
Í
Í
have i ∈I ′ \{ j } s(i) ≤ t. Therefore, i ∈I ′ min{s(i), t} = min{s( j), t} + i ∈I ′ \{ j } s(i) ≤ 2t.
Note also that F̄ is a smooth monotone submodular function; i.e., ∂ F̄(x)/∂ xti ≥ 0 for any t ∈ [T − 1] and i ∈ I,
and ∂ 2 F̄(x)/(∂ xti ∂ xt ′i′ ) ≤ 0 for any t, t ′ ∈ [T − 1] and i, i ′ ∈ I. Hence, we can apply the continuous greedy algorithm
for solving (1). Let x ∗ be an obtained feasible solution for (1). We ﬁrst present a rounding algorithm for this solution.
Since the formulation size of this relaxation is not polynomial, this part does not run in polynomial time. We convert
the algorithm into a polynomial-time one later.
Rounding algorithm: The algorithm consists of two rounds. In the ﬁrst round,
Í each item i chooses an integer t from
[T − 1] with probability xti∗ /4, and chooses no integer with probability 1 − t ∈[T −1] xti∗ /4. An item is discarded if it
chooses no integer. Let I1 be the set of remaining items. For each i ∈ I1 , let ti denote the integer chosen by i.
Then, the algorithm proceeds to the second round. For each i ∈ I1 , let Ji denote { j ∈ I1 : t j ≤ ti }. In the second
round, item i is discarded if s(Ji ) ≥ ti . Let I2 denote the set of items remaining after the second round. The algorithm
outputs a sequence obtained by sorting the items i ∈ I2 in the non-decreasing order of ti , where ties are broken
arbitrarily, and by appending the other items after those in I2 in an arbitrary order.
For t ∈ [T ], let It = {i ∈ I2 : ti ≤ t − s(i) − 1}. If i ∈ It , then i contributes to the objective value of the solution
when the knapsack capacity is at least t.
Lemma 7. For any t ∈ [T ], It is the output of a monotone (1/4, 1/2)-balanced contention resolution scheme for the
maximization problem of f under the knapsack capacity t and the fractional solution x̄t∗ . Hence, the sequence output
by the algorithm achieves an objective value of at least F̄(x ∗ /4)/2 in expectation.
14

Proof. Take arbitrarily t ∈ [T ]. We deﬁne a random mapping π : 2 I → 2 I as follows. Let I ′ ⊆ I. We let each i ∈ I ′
independently sample an integer ti′ from [t − s(i) − 1] with probability xt∗′ i / x̄ti∗ . Deﬁne Ji′ = { j ∈ I ′ : t j′ ≤ ti′ } for each
i
i ∈ I ′. Then, π(I ′) is deﬁned as {i ∈ I ′ : s(Ji′ ) < ti′ }.
Let us see that π is a (1/4, 1/2)-balanced contention resolution scheme for x̄t∗ . For this, we analyze the probability
that i is included in π(Rx̄t∗ /4 ), conditioned that i ∈ Rx̄t∗ /4 . Recall that i ∈ Rx̄t∗ /4 is not included in π(Rx̄t∗ /4 ) if s(Ji′ ) ≥ ti′
Let j be an arbitrary item other than i, and let s ′ ( j) = min{s( j), ti′ }. Notice that s ′ (Ji′ ) ≥ ti′ holds if s(Ji′ ) ≥ ti′ holds. We
give an upper bound on the probability that s ′ (Ji′ ) ≥ ti′ happens. The item j ∈ I \{i} is included in Rx̄t∗ /4 with probability
Í
x̄t∗j /4, and then it is included in Ji′ (i.e., j chooses an integer at most ti′) with probability at most t ′ ∈[ti′ ] xt∗′ j / x̄t∗j . Hence
Í
Í
E[s ′ (Ji′ )] ≤ j ∈I t ′ ∈[ti′ ] xt∗′ j min{s( j), ti′ }/4 ≤ ti′ /2, where the last inequality follows from the second constraint of
(1). Applying Markov’s inequality, we obtain Pr[s ′ (Ji′ ) ≥ ti′] ≤ 1/2. Therefore, Pr[i ∈ π(Rx̄t∗/4 ) | i ∈ Rx̄t∗ /4 ] ≥ 1/2,
∗
which means that π is a (1/4, 1/2)-balanced contention resolution
Í scheme′ for x̄t .
′
′′
Next, we prove that π is monotone. Let I ⊆ I ⊆ I. Then, j ∈Ji′ s(i ) is not smaller in the computation of π(I ′′)
than in the computation of π(I ′), if each item in I ′ samples the same integer both in π(I ′) and π(I ′′). This implies
Pr[i ∈ π(I ′)] ≥ Pr[i ∈ π(I ′′ )] for each i ∈ I ′ . Thus, π is monotone.
Let us observe that It coincides with π(Rx̄t∗ /4 ). Recall that, in the ﬁrst round of the algorithm, each item i
Í
independently chooses an integer ti . The probability that ti ≤ t − s(i) − 1 is t ′ ∈[t−s(i)−1] xti∗ /4 = x̄ti∗ /4. Hence, item set
{i ∈ I : ti ≤ t − s(i)−1} coincides with Rx̄t∗/4 . Then, the decision of whether or not an item i in this set is discarded in the
second round of the algorithm is the same as the computation of π(Rx̄t∗ /4 ). Therefore, It coincides with π(Rx̄t∗ /4 ). 
√
By Theorem 1 and Lemma 7, our algorithm achieves ((1 − 1/ 4 e)/2 − o(1))-approximation if it is combined with
the continuous greedy algorithm with stopping time 1/4.
Lemma 7 also implies that the integrality gap of (1) is at least 1/8. On the other hand, there exist some instances
indicating that the integrality gap is at most 1/3 + ǫ for any ǫ > 0 even when the objective function is modular. Suppose
that the capacity is T > 1 with probability 1, and there are three items: two items i and j of size T , and an item k
of size 1. The weight of these items are all 1, and the objective value is deﬁned as the sum of the weights of chosen
items. Clearly a knapsack of capacity T can include at most one of the items, and hence the maximum objective value
of integer solutions is 1. On the other hand, a fractional solution deﬁned by x0i = 1, x0j = (T − 1)/T , xT −1,k = 1 and
setting the other variables to be 0 achieves the objective value 3 − 1/T .
Conversion into a polynomial-time algorithm: We transform the pseudo-polynomial algorithm into the polynomialtime one. Let W = f (I) and w = mini ∈I f ({i}). We assume w > 0 without loss of generality; if f ({i}) = 0 for some
item i ∈ I, we can safely remove i from I because the submodularity implies f (S) = 0 for any S ⊆ I with i ∈ S.
Recall that we assume that the submodular function f is given as an oracle. Indeed, algorithms in this paper can be
implemented if we can compute the value of the function (or the value of its multilinear extension). We assume that
the oracle is encoded in Ω(log(W/w)), and hence we say that an algorithm runs in polynomial time if its running time
is expressed as a polynomial in log(W/w).
The idea for the conversion is to use a more compact relaxation, which is obtained by deﬁning variables and
constraints for a polynomial number of integers in [T ]. LetÍǫ be a positive constant smaller than 1, and let η =
⌊log1−ǫ (ǫw/(W log T ))⌋. For each t ∈ [T − 1], let p̄(t) denote Tt′=t+1 p(t ′). We ﬁrst deﬁne {τ0, τ1, . . . , τq, τq+1 } ⊆ [T ]
such that q = O(log T + log(W/(wǫ))), τ0 = 0, τ1 = 1, τq+1 = T , τj < τj+1 ≤ 2τj holds for any j = 1, . . . , q, and there
exists qη ∈ {1, . . . , q} satisfying the following conditions:
• p̄(τj ) ≥ p̄(τj+1 − 1) ≥ (1 − ǫ) p̄(τj ) for any j ∈ [qη ];
• p̄(τj ) < ǫw/(W log T ) for any j ∈ {qη + 1, . . . , q}.
Such a subset of [T ] can be deﬁned as follows. For j ∈ {1, . . . , η + 1}, let τj′ be the minimum integer t ∈ [T − 1] such
that p̄(t) < (1 − ǫ) j−1 . We assume without loss of generality that p̄(mini ∈I s(i)) = 1, which means τ1′ ≥ mini ∈I s(i). We
denote the set of positive integers in {τj′ : j = 1, . . . , η + 1} ∪ {2 j : j ∈ [⌈log T ⌉ − 1]} by {τ1, . . . , τq }, and sort those
′ . Then, the obtained subset satisﬁes the above
integers so that 1 = τ1 < τ2 < · · · < τq . We deﬁne qη so that τqη = τη+1
conditions.
In addition, we deﬁne the set of integers in {τ0, . . . , τq+1 } ∪ {τj − s(i) +1 : j ∈ {1, . . . , q +1}, i ∈ I } as {ξ0, . . . , ξr+1 },
where 0 = ξ0 < ξ1 < . . . < ξr < ξr+1 = T . Notice that r = O(n log T + n log(W/(wǫ))).
Roughly speaking, we deﬁne variables for each ξk (k ∈ [r]), and constraints for each τj ( j ∈ [q]). Speciﬁcally, a
variable yki is deﬁned for each k ∈ [r] and i ∈ I, and yki replaces variables xξk ,i , . . . , xξk+1 −1,i in (1). For j = 1, . . . , q +1
15

Í
and i ∈ I, we deﬁne an auxiliary variable z ji as ξk+1 −1≤τ j −s(i) yki , and deﬁne z j as the |I |-dimensional vector whose
component corresponding to i ∈ I is z ji . Then, the compact relaxation is described as follows.
Íq
p̄(τj )(F(z j+1 ) − F(z j ))
maximize
Í j=0
y ≤ 1,
∀i ∈ I,
subject to
Ík ∈[r]Í ki
y
min{s(i),
τ
}
≤
2τ
,
∀ j ∈ {1, . . . , q},
(2)
j
j
i ∈I Íξk <τ j ki
∀ j ∈ [q],
z ji = ξk+1 −1≤τ j −s(i) yki
yki ≥ 0,
∀i ∈ I, ∀k ∈ [r].
Lemma 8. The optimal objective value of (2) is not smaller than that of (1).

Íξk+1 −1
xti
Proof. Suppose that x is a feasible solution for (1). From x, we deﬁne a solution y for (2) so that yki = t=ξ
k
for each k ∈ [r] and i ∈ I. We deﬁne variables z from y by the third constraints of (2). Then, (y, z) is feasible to (2).
Indeed, it is immediate from the feasibility of x inÍ
(1) that (y, z)Í
satisﬁes the constraints of (2) except the second one.
As for the second constraints, we can observe that ξk <τ j yki = t <τ j xti holds for any i ∈ I and j ∈ {1, . . . , q} by the
deﬁnition of y and the fact that τj is included in {ξ1, . . . , ξr }.
Let us show that the objective value of (y, z) in (2) is not smaller than F̄(x). We have
F̄(x) =

T
Õ
t=1

p(t)F( x̄t ) = p̄(T − 1)F( x̄T ) +

T
−1
Õ
t=1

( p̄(t − 1) − p̄(t))F( x̄t ) =

T
−1
Õ
t=0

p̄(t)(F( x̄t+1) − F( x̄t )),

where x̄0 denotes the zero-vector for convention. The right-hand side can be written as
T
−1
Õ
t=0

p̄(t)(F( x̄t+1) − F( x̄t )) =
≤
=

q τÕ
j+1 −1
Õ
j=0 t=τ j

q τÕ
j+1 −1
Õ

j=0 t=τ j
q
Õ
j=0

p̄(t)(F( x̄t+1) − F( x̄t ))
p̄(τj )(F( x̄t+1) − F( x̄t ))

p̄(τj )(F( x̄τ j+1 ) − F( x̄τ j )).

(3)

Í
for each j ∈ [q] and i ∈ I. There exists k ′ ∈ [r] such that τj − s(i) + 1 = ξk ′ , and hence
Recall that x̄τ j i = t ≤τ j −s(i) xti Í
Í
t ≤τ j −s(i) xti can be written as ξk −1≤τ j −s(i) yki = z ji . Thus x̄τ j = z j holds for each j ∈ [q], implying that (3) is equal
to the objective value of (y, z).

Lemma 9. From a feasible solution to (2) achieving the objective value θ, we can construct a feasible solution to (1)
achieving the objective value of at least (1 − ǫ)(θ − ǫw)/2.
Proof. Let (y, z) be a feasible solution to (2). For each k ∈ [r], i ∈ I, and t ∈ {ξk , . . . , ξk+1 − 1}, we deﬁne xti as
yki /(ξk+1 − ξk ).
We prove that x/2 is feasible to (1). It is immediate from the deﬁnition of x that x satisﬁes the ﬁrst and the third
constraints of (1). We focus on the second constraints. Let t ∈ {1, . . . , T − 1}. Suppose that τj ≤ t < τj+1 holds for
Í
Í
Í
some j ∈ [q]. Then, for each i ∈ I, we have t ′ ∈[t] xt ′ i ≤ t ′ <τ j+1 xt ′ i = ξk <τ j+1 yki , where the equality follows from
the fact that τj+1 ∈ {ξ1, . . . , ξr+1 }. Moreover, min{s(i), t} ≤ min{s(i), τj+1 } also holds. Hence,
ÕÕ
Õ Õ
yki min{s(i), τj+1 } ≤ 2τj+1
xt ′i min{s(i), t} ≤
i ∈I t ′ ∈[t]

i ∈I ξk <τ j+1

Í
holds, where the last inequality follows from the second constraints of (2) when j < q, and from τq+1 = T = i ∈I s(i)
and the ﬁrst constraints of (2) when j = q. By its deﬁnition, t ≥ τj ≥ τj+1 /2. This implies that x/2 is feasible to (1).
Let θ be the objective value of (y, z) in (2). We show that the objective value F̄(x/2) of x/2 in (1) is at least
(1 − ǫ)(θ − ǫw)/2. We observe that
F̄

x
2

=

T
Õ
t=1

p(t)F



x̄t
2



≥

q τ j+1 −1
T
1Õ Õ
1Õ
p̄(t) (F ( x̄t+1 ) − F ( x̄t )) .
p(t)F ( x̄t ) =
2 t=1
2 j=0 t=τ
j

16

Since p̄(t) ≥ p̄(τj+1 − 1) for any t ≤ τj+1 − 1, the right-hand side of the above inequality satisﬁes

τÕ
q τ j+1 −1
q
j+1 −1
1Õ Õ
1Õ
p̄(t) (F ( x̄t+1 ) − F ( x̄t )) ≥
(F ( x̄t+1 ) − F ( x̄t ))
p̄(τj+1 − 1)
2 j=0 t=τ
2 j=0
t=τ
j

=

1
2

q
Õ
j=0

j



p̄(τj+1 − 1) F x̄τ j+1 − F x̄τ j .


Recall that x̄τ j = z j and p̄(τj+1 − 1) ≥ (1 − ǫ) p̄(τj ) hold for any j ∈ [qη ]. Therefore,

qη
q


 1 − ǫ Õ


1Õ
p̄(τj+1 − 1) F x̄τ j+1 − F x̄τ j ≥
p̄(τj ) F z j+1 − F z j .
2 j=0
2 j=0

On the other hand, θ can be written as
θ=

q
Õ
j=0

p̄(τj )(F(z j+1 ) − F(z j )) =

qη
Õ
j=0

p̄(τj )(F(z j+1) − F(z j )) +

q
Õ

j=qη +1

p̄(τj )(F(z j+1) − F(z j )).

Recall that p̄(τj ) ≤ ǫw/(W log T ) if j ≥ qη + 1. Moreover, we have q − qη ≤ log T , and hence
q
Õ

j=qη +1

p̄(τj )(F(z j+1) − F(z j )) ≤

q
Õ

j=qη +1

Combining all these discussion, we have F̄(x/2) ≥ (1 − ǫ)(θ − ǫw)/2.

p̄(τj )W ≤ ǫw.


We now wrap up our algorithm. Our algorithm ﬁrst applies the continuous greedy algorithm with
√ stopping time
1/4 to compute a solution y such that 4y is feasible for (2) and the objective value of y in (2) is 1 − 1/ 4 e times that of
any feasible solution, particularly the optimal value h of (2). From y, we compute a solution
√ x for (1) by Lemma 9.
We see that 4x is feasible for (1), and the objective value of x in (1) is at least (1 − ǫ)((1 − 1/ 4 e)h − ǫw)/2. Since we
are assuming p̄(mini ∈I s(i)) ≥ 1, picking the item of the smallest size at√time 0 achieves objective value w. This means
h ≥ w, and hence the objective value of x is at least (1 − ǫ)(1√− ǫ − 1/ 4 e)h/2. Then, applying the rounding algorithm
to 4x, we obtain a sequence of objective value (1 − ǫ)(1 − 1/ 4 e − ǫ)h/4.
To make this algorithm run in polynomial-time, we do not explicitly write down x. In the rounding algorithm,
values of x are used for deciding ti for each i ∈ I in the ﬁrst round of the rounding algorithm. This is possible
without writing down x as follows. Notice that xti takes the same value for any t ∈ [τj , τj+1 ) by the construction of
x. Hence each i chooses ti as follows. First, i chooses k ∈ [q] with probability yki , and is discarded with probability
Í
1 − k ∈[r] yki . Then, i chooses ti from [τk , τk+1 ) uniformly at random. This algorithm runs in polynomial time with
respect to 1/ǫ and the input size of the instance. We give a pseudo-code of the algorithm in Algorithm 5.
With the conversion given above, we obtain the following theorem.
Theorem 9. For any
√ constant ǫ ∈ (0, 1), there exists a randomized approximation algorithm of approximation ratio
(1 − ǫ)(1 − ǫ − 1/ 4 e)/4 − o(1) ≈ 0.055 − ǫ for SMPSC, which runs in polynomial time with respect to 1/ǫ and the
input size of the instance.

6 Conclusion
We considered the maximization problem of a nonnegative monotone submodular function under an unknown or a
stochastic knapsack constraint. We presented adaptive policies that achieve constant robustness ratios for an unknown
knapsack constraint when the cancellation is allowed. For the case where the cancellation is not allowed, we presented
approximation algorithms that achieve constant approximation ratios for a stochastic knapsack constraint.
There still remain many interesting directions of further studies. We mention two of them here. First, even for
KPUC with cancellation, there is still a gap between the best known upper and lower bounds on the robustness ratio if
we consider randomized policies; the best known lower bound is 1/2 achieved by the deterministic policy of Disser et
17

√
Algorithm 5: Randomized algorithm of approximation ratio (1 − ǫ)(1 − ǫ − 1/ 4 e)/4 − o(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

for ∀ j ∈ {1, . . . , η + 1} do
compute τj′ = arg min{t ∈ [T − 1] : p̄(t) < (1 − ǫ) j−1 } by the binary search

compute τ0, . . . , τq+1 , qη , and ξ0, . . . , ξr+1 ;
y ← output of the continuous greedy with stopping time 1/4 applied to (2);
I ′ ← ∅;
for i ∈ I do
Í
choose a number k from [q] with probability yki or I ′ ← I ′ ∪ {i} with probability 1 − k ∈[q] yki ;
if i < I ′ then choose an integer ti from [τk , τk+1 ) uniformly at random;

Π ′ ← sequence obtained by sorting the items i ∈ I \ I ′ in a non-decreasing order of ti ;
Π ← (Π1′ ), l ← 2;
for i = 2, . . . , |Π ′ | do
Í
if j ∈[i−1] s(Π ′j ) < tΠ′i then Πl ← Πi′ , l ← l + 1 ;
else I ′ ← I ′ ∪ {Πi′ } ;
append the items in I ′ to the suﬃx of Π arbitrarily, and return Π;

al. [6], and we give an upper bound 8/9 in Section 4.1. Hence it is an interesting direction to investigate whether there
exists a randomized policy achieving a robustness ratio better than 1/2.
Another interesting future work is to investigate an upper bound on the robustness ratio of SMPUC with cancellation.
The best known upper bound on the robustness ratio achieved by the deterministic policies is 1/2 which is given by
an instance of KPUC. Although this is tight for deterministic policies to KPUC even if they are restricted to universal
policies, it may be possible to give a smaller upper bound if we consider submodular objective functions. It is interesting
to investigate whether an upper bound smaller than 1/2 is achievable for SMPUC.
Acknowledgement: The ﬁrst author is supported by JSPS KAKENHI Grant Number JP16K16005. The second
author is supported by JSPS KAKENHI Grant Number JP17K12646 and JST ERATO Grant Number JPMJER1201,
Japan. The third author is supported by JSPS KAKENHI Grant Number JP17K00040 and JST ERATO Grant Number
JPMJER1201, Japan.

References
[1] M. Adamczyk, M. Sviridenko, and J. Ward. Submodular stochastic probing on matroids. Math. Oper. Res.,
41(3):1022–1038, 2016.
[2] A. Asadpour, H. Nazerzadeh, and A. Saberi. Stochastic submodular maximization. In Internet and Network
Economics, 4th International Workshop, WINE 2008, Shanghai, China, December 17-20, 2008. Proceedings,
pages 477–489, 2008.
[3] G. Călinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a monotone submodular function subject to a
matroid constraint. SIAM J. Comput., 40(6):1740–1766, 2011.
[4] M. Dabney. A PTAS for the uncertain capacity knapsack problem. Master’s thesis, Clemson University, 2010.
[5] B. C. Dean, M. X. Goemans, and J. Vondrák. Approximating the stochastic knapsack problem: The beneﬁt of
adaptivity. Math. Oper. Res., 33(4):945–964, 2008.
[6] Y. Disser, M. Klimm, N. Megow, and S. Stiller. Packing a knapsack of unknown capacity. SIAM J. Discrete
Math., 31(3):1477–1497, 2017.
[7] M. Feldman. Maximization Problems with Submodular Objective Functions. PhD thesis, Technion – Israel
Institute of Technology, July 2013.

18

[8] M. Feldman, J. Naor, and R. Schwartz. A uniﬁed continuous greedy algorithm for submodular maximization.
In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA,
October 22-25, 2011, pages 570–579, 2011.
[9] M. Feldman, O. Svensson, and R. Zenklusen. Online contention resolution schemes. In Proceedings of the TwentySeventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12,
2016, pages 1014–1033, 2016.
[10] D. Golovin and A. Krause. Adaptive submodularity: Theory and applications in active learning and stochastic
optimization. J. Artif. Intell. Res. (JAIR), 42:427–486, 2011.
[11] A. Gupta, R. Krishnaswamy, M. Molinaro, and R. Ravi. Approximation algorithms for correlated knapsacks and
non-martingale bandits. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011,
Palm Springs, CA, USA, October 22-25, 2011, pages 827–836, 2011.
[12] A. Gupta, V. Nagarajan, and S. Singla. Adaptivity gaps for stochastic probing: Submodular and XOS functions.
In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017,
Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1688–1702, 2017.
[13] W. Höhn and T. Jacobs. On the performance of Smith’s rule in single-machine scheduling with nonlinear cost.
ACM Trans. Algorithms, 11(4):25:1–25:30, 2015.
[14] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. M. VanBriesen, and N. S. Glance. Cost-eﬀective outbreak
detection in networks. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining, San Jose, California, USA, August 12-15, 2007, pages 420–429, 2007.
[15] W. Ma. Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms: Extended abstract. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1154–1163, 2014.
[16] N. Megow and J. Mestre. Instance-sensitive robustness guarantees for sequencing with unknown packing and
covering constraints. In Innovations in Theoretical Computer Science, ITCS ’13, Berkeley, CA, USA, January
9-12, 2013, pages 495–504, 2013.
[17] N. Megow and J. Verschae. Dual techniques for scheduling on a machine with varying speed. In Automata,
Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013,
Proceedings, Part I, pages 745–756, 2013.
[18] M. Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res.
Lett., 32(1):41–43, 2004.
[19] A. C. Yao. Probabilistic computations: Toward a uniﬁed measure of complexity (extended abstract). In 18th
Annual Symposium on Foundations of Computer Science, Providence, Rhode Island, USA, 31 October - 1
November 1977, pages 222–227, 1977.

19

