4810-1183: Approximation and Online Algorithms with Applications
Lecture Note 3: Approximation Algorithm for Knapsack Problem
Problem Definition
Suppose that you are in an all-you-can-eat strawberry farm, where you can have an unlimited amountof strawberry. Such type of farms are quite common in Japan, but, recently, many customers have a badhabit leaving a lot of remaining strawberry. Because of that, the association of all-you-can-eat
strawberry farms issues a rule to prohibit leaving a partly-eaten strawberry. When you decide to eat astrawberry, you have to each a whole of it.
We have the following optimization model, because we want to eat the maximum amount ofstrawberry.
Input:

Positive integer 𝑛 (number of strawberries)
Positive real numbers 𝑤1 , … , 𝑤𝑛 (weight of each strawberry)
Positive real number 𝑊 (maximum amount that we can eat strawberry)
Assumption: 𝑤1 ≤ 𝑤2 ≤ ⋯ ≤ 𝑤𝑛

Output:Set 𝑆 ⊆ {1, … , 𝑛} (set of strawberry we eat)

Constraint:∑𝑖∈𝑆 𝑤𝑖 ≤ 𝑊 (the weight sum of strawberry we eat is no more than 𝑊.)

Objective Function:

Maximize ∑𝑖∈𝑆 𝑤𝑖 (maximize the amount of strawberry we eat.)

For example, when 𝑛 = 5, 𝑤1 = 2, 𝑤2 = 5, 𝑤3 = 5, 𝑤4 = 6, 𝑤5 = 9 , 𝑊 = 10 , we should eat
strawberry 2 and 3 to gain the maximum eating amount 𝑤2 + 𝑤3 = 10 = 𝑊. We attain the best output
when 𝑆 = {2,3}.
Corresponding to any particular output, the objective function gives us a value which we call“objective value”. For example, the objective value of 𝑆 = {1,2} is 𝑤1 + 𝑤2 = 7. The best objective
value we can get from a particular input is called “optimal value”. We look for outputs with the objective
value equal to the optimal value, and we will call those outputs as “optimal solutions”. During thiscourse, we will sometimes denote the optimal value by 𝑂𝑃𝑇, and sometimes denote the optimal solution
by 𝑆 ∗.
The above problem is the simplified version of a problem called knapsack. The problem isknown to be NP-hard even for the simplified version.
Algorithm
The following algorithm is for the simplified knapsack problem:
1:
2:
3:
4:
5:
6:
7:
8:

𝑆←∅
For 𝑗 = 1 to 𝑛
If ∑𝑖∈𝑆 𝑤𝑖 + 𝑤𝑗 ≤ 𝑊:
𝑆 ← 𝑆 ∪ {𝑗}Else:
if 𝑤𝑗 ≥ ∑𝑖∈𝑆 𝑤𝑖 :𝑆 ← {𝑗}break

The algorithm is mostly greedy algorithm. From the smallest to the heaviest, we pickstrawberries to a bucket until the weight sum is more than we can eat. As, at the last step, we have morethan we can eat in the bucket, we will remove some strawberry. We will remove the last strawberrywhen the weight of the last is smaller than that of the others combined. Otherwise, we will remove all
but the last strawberry.
Recall the example in the previous section. We will choose strawberry 1, 2, and 3 into ourbucket. After we have strawberry 3, the weight sum (𝑤1 + 𝑤2 + 𝑤3 = 12) is more than 𝑊 = 10. We
have to choose between removing strawberry 3 or removing strawberry 1, 2. We will be able to eat
more if we choose to remove strawberry 3, so we remain strawberry 1, 2 in our bucket. The output of
the algorithm is 𝑆 = {1,2}, and the objective value of the input is 7.
In this course, we will denote an input of an algorithm by 𝑆′, and denote its objective value by
𝑆𝑂𝐿. 𝑆′ is fairly nice, but it is not one of the optimal solutions as 𝑆𝑂𝐿 < 𝑂𝑃𝑇. However, we can prove
the following theorem.
Theorem 1: For any input, 𝑆𝑂𝐿 ≥ 0.5 ⋅ 𝑂𝑃𝑇.
Proof: It is straightforward to show that 𝑂𝑃𝑇 ≤ 𝑊. We cannot eat more than 𝑊 even in the optimal
solution, as 𝑊 is our maximum capacity.
In the algorithm, we will pick the strawberries until the weight sum is more than 𝑊. We know
that
Weight sum of other strawberries + weight of the last strawberry ≥ 𝑊.
By the inequality, we know that either “weight sum of other strawberries” or “weight of the laststrawberry” is more than 0.5 ⋅ 𝑊. If both of them are smaller than 0.5 ⋅ 𝑊, the sum of them will not be
more than 𝑊. Because of that, if we take the larger of the two, we will have the remaining weight larger
than 0.5 ⋅ 𝑊. We have 𝑆𝑂𝐿 ≥ 0.5 ⋅ 𝑊 ≥ 0.5 ⋅ 𝑂𝑃𝑇.

Approximation Algorithm
Suppose that 𝛼 is a positive real number less than 1. We will say that an algorithm is “an 𝛼 approximation algorithm” for a particular problem, if, for all inputs, we have
𝑆𝑂𝐿 ≥ 𝛼 ⋅ 𝑂𝑃𝑇.
When we want to find an output that maximize a value, 𝑂𝑃𝑇 is the maximum objective value we canhave from a particular input. Clearly, 𝑆𝑂𝐿, which is an arbitrary object value, cannot be larger than
𝑂𝑃𝑇. If we can solve the problem, we will have 𝑆𝑂𝐿 = 𝑂𝑃𝑇 for all inputs. However, that is not possible
when the problem is NP-hard. We unfortunately have 𝑆𝑂𝐿 < 𝑂𝑃𝑇 for some input. Still, we cantheoretically guarantee that 𝑆𝑂𝐿 is always larger than 50% of 𝑂𝑃𝑇 when 𝛼 = 0.5.
The guarantee can infer that, when we have an input with large optimal values, we are very
likely to have a large objective value from our algorithm. You might wonder why we have to careproving the inequality in the previous paragraph. The reason is, when you propose a method and you
have only experiment results to support that the method is good, people cannot be sure if the results willbe also good for their dataset or situations. They might not want to take risks implementing yourmethods, and your work might not be recognized as it should be. Because, with theories, people caneasily know strong points and limitations of your methods, we do invite you to try having someguarantee for any of your proposals.
Approxability is one of the most common guarantee for an NP-hard problem [1]. We call 𝛼 an“approximation ratio” of our algorithm.

Knapsack Problem
Previously, we want to maximize the strawberry weight we take. That is not something you usuallywant to maximize in practice. Some strawberries might be more delicious than others, and we mightwant to eat them than just maximize the weight sum. Let suppose that we know our “happiness” fromeating each strawberry in advance. We may formalize the problem into the following optimization
model:
Positive integer 𝑛 (number of strawberries)
Positive real numbers 𝑤1 , … , 𝑤𝑛 (weight of each strawberry)
Positive real number 𝑊 (maximum amount that we can eat strawberry)
Positive real number 𝒉𝟏 , … , 𝒉𝒏 (happiness from eating each strawberry)

Input:𝒉𝒉𝒉Assumption: 𝒘𝟏 ≥ 𝒘𝟐 ≥ ⋯ ≥ 𝒘𝒏
𝟏

𝟐𝒏

Output:Set 𝑆 ⊆ {1, … , 𝑛} (set of strawberry we eat)

Constraint:∑𝑖∈𝑆 𝑤𝑖 ≤ 𝑊 (the weight sum of strawberry we eat is no more than 𝑊.)

Objective Function:

Maximize ∑𝒊∈𝑺 𝒉𝒊(maximize the happiness from the strawberries we eat.)

The differences from the simplified version previously discussed are marked in bold italic.
Instead of assuming that a smaller strawberry will come before a larger one, we sort the strawberries by
the happiness gained per weight consumed. It is straightforward to show that the knapsack problem is
NP-hard based on the fact that the simplified version is NP-hard.
We have the following algorithm for the knapsack problem.
1:
2:
3:
4:
5:
6:
7:
8:

𝑆←∅
For 𝑗 = 1 to 𝑛
If ∑𝑖∈𝑆 𝑤𝑖 + 𝑤𝑗 ≤ 𝑊:
𝑆 ← 𝑆 ∪ {𝑗}Else:if 𝒉𝒋 ≥ ∑𝒊∈𝑺 𝒉𝒊 :𝑆 ← {𝑗}break

The only difference from the previous algorithm in at Line 6. Previously, we chose to remove the laststrawberry or the others based on the strawberries’ weight. Now, we choose based on the strawberries’
happiness. We will choose to remove the last strawberry if the happiness sum of the others are larger,
and we will choose to remove the others if the happiness of the last strawberry is larger.
We can prove that the algorithm is 0.5-approximation algorithm, which mean that, for any
particular input, the happiness we have from the algorithm is no less than 50% of the optimal. We will
skip the proof in this course.
Bloom Filters
We will now move to an application on distributed computing. Consider the situation that we have acache for a very dynamic network. There is a large number of data contained in the cache, and there area very large number of inquiries if a particular data is there. We need a data structure that can answer
to those inquiries in a few nanoseconds. If we use a sequential data structure like linked list, we might
have to check all data in the worst case. That will take us too much searching time.

Suppose that all the possible data can be denoted by a positive integer less than 1080. (Theinteger can be conversed from a 256-bit string, which represent the short description of each data.) We
can have an array of booleans a with length 1080. At the beginning, we set all a[i] to false. When we
add an element i to the cache, we set a[i] to true. If there is an inquiry if i’ is in the cache, we canimmediately return a[i’].
The method mentioned in the previous paragraph is very efficient. We can immediately update
the array a, and the inquiry is answered almost immediately. However, it consumes a large amount ofmemory. We need 1080 bits for the data structure, and we are very unlikely to have to that large memory.
We can use hash functions to help us reduce the memory consumption. Suppose that the arraysize is 𝑚, which is much smaller 1080. When we enter a particular information 𝑖 to our cache, we will
use the hash function 𝑓 to map 𝑖 to a random integer between 0 to 𝑚 − 1. Then, we will set a[f(i)]to true. When we have an inquiry if 𝑖′ is in the cache, we will return a[f(i’)].
We assume that, for every information 𝑖, 𝑓(𝑖) equals any integer between 0 to 𝑚 − 1 withprobability 1/𝑚. Because of that, there will be about 1080 /𝑚 of information such that the hash of theinformation equals a particular number 𝑗. When a[f(i)]=false, we will be sure that we have not 𝑖in the cache. If 𝑖 is put to the cache, a[f(i)]should have been set to true. On the other hand, ifa[f(i)]=true, things might be more difficult. a[f(i)] might have been set to true because 𝑖′ isentered to the cache, or it might be because of other 1080 /𝑚 information 𝑖′ that have 𝑓(𝑖) = 𝑓(𝑖 ′ ).
Inspired by machine learning, we call the situation in the previous paragraph as false positive.
Let us try to understand why the false positive is not good for a web cache system. In the system, users
will search for a content with a particular URL in a cache. We usually have 2 layers of computations in
the cache. The first layer will have a short description of a website, and answer if we have that website
in the cache. Then, if there is, we will move to the second layer. We will search for the full web content
and return the whole web content to users. We aim to design an algorithm for the first layer, which iscalled as “filter” here. When we frequently have false positive at the filter, we frequently have to moveto the calculation at the second layer, which is much heavier. Thus, we do not want to have a lot of false
positive, as it will decrease the efficiency of the cache system.
Let us try to calculate the probability of having a false positive. We will calculate a probability
that the filter will return true, when we search for an information 𝑖 that is not in the cache. Suppose that
there are 𝑛 different information in the cache, denoted by 𝑖1′ , … , 𝑖𝑛′ . We will have a[f(i)] = true
if and only if, for some 𝑘, we have 𝑓(𝑖) = 𝑓(𝑖𝑘′ ). By contrapositive, we will have a[f(i)] = false
if and only if, for all 𝑘, we have 𝑓(𝑖) ≠ 𝑓(𝑖𝑘′ ). Because the hash function 𝑓 gives us a uniform random
1
1number, the probability that 𝑓(𝑖𝑘′ ) equals to a particular value is . 𝑓(𝑖𝑘′ ) = 𝑓(𝑖) with probability .
𝑚
𝑚
1
′)
′)
Thus, for a particular 𝑘, 𝑓(𝑖𝑘 ≠ 𝑓(𝑖) with probability 1 − 𝑚. We can consider the event when 𝑓(𝑖𝑘 ≠𝑓(𝑖) for each 𝑘 as independent events. Because there is 𝑛 possible values for 𝑘, there are 𝑛 events with
1 𝑛

1

the same probability 1 − 𝑚. The probability of having all events occurred is (1 − 𝑚) . By that, the
1 𝑛probability of having a[f(i)] = false is (1 − 𝑚) . The probability of having a[f(i)] =1 𝑛true, false positive, is 1 − (1 − 𝑚) .

The probability of having false positive, which is a bad situation leading to a large
computational cost, in the previous paragraph is usually very close to 1. It is very important to decreasethat probability. There is a technique that help decreasing the probability called “bloom filter” [2].
Previously, we have just one hash function. Let us use 𝑝 totally independent hash functions 𝑓1 , … , 𝑓𝑝 .
When we have a new information 𝑖 in the case, we will set all a[f1(i)], …, a[fp(i)] totrue .When there is an inquiry if 𝑖 is in the cache, we will answer that 𝑖 is in the cache if and only ifa[f1(i)], …, a[fp(i)] are all true. We will answer that 𝑖 is not in the cache otherwise.
We will have a false positive, only if all 𝑝 bits are not correct. When 𝑝 becomes larger, having
all 𝑝 bits incorrect are less likely to happen. On the other hand, when 𝑝 becomes larger, we have toassign more bits to 1. For example, if 𝑝 ≫ 𝑚, we will have all elements of the array becomes 1 by justone information. We have false positives from any queries after that. It is a trade-off between how much
we can confirm and how many true bits in the array. The main goal of this section is to calculate whatis the best value of 𝑝.
Again, we will suppose that an information 𝑖 is not in the cache. We want to calculate theprobability that our filter will report that 𝑖 is in the cache. Let us consider the probability that a particulara[j] is set to true. Because we have 𝑛 different information in the cache and, when we have new
information, we will assign true to 𝑝 places, the event of assigning true happens for 𝑛 ⋅ 𝑝 times. Each1event will not hit a[j] with probability (1 − 𝑚), so the probability of having all 𝑛 ⋅ 𝑝 events not
1 𝑛𝑝

1 𝑛𝑝

hitting a[j] is (1 − 𝑚) . For all 𝑗, a[j]=false with probability (1 − 𝑚) , so a[j]=true
1 𝑛𝑝. For each 𝑞 , we have a[fq(i)]=true𝑚with probability 1 − (1 − )with probability 1 −1 𝑛𝑝(1 − ) , and a[f1(i)],𝑚…, a[fp(i)] are all true with probability (1 − (1 − ) ) . The

1 𝑛𝑝
𝑚

𝑝
1 𝑛𝑝

𝑝

probability of having false positive is (1 − (1 − 𝑚) ) .
We can use calculus to find the best value of 𝑝, and it turns out that we will minimize the𝑚probability of having false positive when 𝑝 = 𝑛 ⋅ ln 2.
Adaptive Bloom Filter
Let us now consider the situation where we know the probability that each information 𝑖 is in the cache.
As the internet provider sometimes refresh the bloom filter to an empty array, the probability could be
predicted from the caches before the refreshes. We denote the probability of having 𝑖 in the cache as 𝑃𝑖 .
With different probability, the number of a[j] we will set to true for different information 𝑖is going to be different. Assume that we set 𝑝𝑖 bits for an information 𝑖 and the set of information in thecache is 𝑆. The number of events we set some random a[j] to true is ∑𝑖∈𝑆 𝑝𝑖 . The probability that an
1 ∑𝑖∈𝑆 𝑝𝑖

arbitrary a[j] is not set during those events is (1 − 𝑚)

. The authors of [2] have the following

theorem:
Theorem 2: The probability of false positive is minimized, if the probability that a[j]=true is 0.5.
1 ∑𝑖∈𝑆 𝑝𝑖

Because of that, to minimize the probability of false positive, we want to have (1 − 𝑚)=

10.5. That is (∑𝑖∈𝑆 𝑝𝑖 ) ⋅ ln (1 − 𝑚) = ln 0.5. As we know that 1 − 𝑥 is very close to 𝑒 −𝑥 for a very small
11
positive real number 𝑥, we have 1 − ≈ 𝑒 −𝑚 . Then,
𝑚
1
𝑚

1

1
𝑚

(∑𝑖∈𝑆 𝑝𝑖 ) ⋅ ln (1 − ) ≈ (∑𝑖∈𝑆 𝑝𝑖 ) ⋅ ln (𝑒 −𝑚 ) = (∑𝑖∈𝑆 𝑝𝑖 ) (− ) = ln 0.5.

If we negate both sides of the equation, we have1
∑ 𝑝𝑖 = − ln 0.5 = ln 2.
𝑚𝑖∈𝑆Because of the derivation, we want to have ∑𝑖∈𝑆 𝑝𝑖 = 𝑚 ⋅ ln 2.
When we decide the value of 𝑝𝑖 for each information, it is just a design step. We have not yet
got an information in the cache, and we do not know what 𝑆 is. Because of that, we cannot explicitly
calculate the value of ∑𝑖∈𝑆 𝑝𝑖 . However, because we know that the probability of having 𝑖 ∈ 𝑆 is 𝑃𝑖 ,we can estimate the value of ∑𝑖∈𝑆 𝑝𝑖 by ∑𝑖 𝑃𝑖 ⋅ 𝑝𝑖 . After a long discussion, we want to have the following
equation.
∑ 𝑃𝑖 ⋅ 𝑝𝑖 = 𝑚 ⋅ ln 2.
𝑖Now, let us consider the probability of having false positive. Recall that, for each 𝑗 , theprobability of having a[j]=true is 0.5. Because, for an information 𝑖 not in the cache, we have tocheck 𝑝𝑖 bits, the probability of having all 𝑝𝑖 bits true is (0.5)𝑝𝑖 . When we assume that all information
are inquired exactly one time, the expect number of false positive is ∑𝑖(0.5)𝑝𝑖 . Because we want to
optimize the number of false positive, we have the following optimization model:
Input:For all information 𝑖, probability 𝑃𝑖 (probability that we have 𝑖 in 𝑆)
positive integer 𝑚 (cache size)

Output:For all information 𝑖, positive integer 𝑝𝑖(number of random bits set to true when 𝑖 arrives to cache)Constraint:∑𝑖 𝑃𝑖 ⋅ 𝑝𝑖 = 𝑚 ⋅ ln 2.

Objective Function:

Minimize ∑𝑖(0.5)𝑝𝑖

Let us consider the objective function ∑𝑖(0.5)𝑝𝑖 . We usually have a problem when the function
is exponential of output, so we need something easier. Assume that the number of random bits set to
(1)

(2)

(3)

true when a particular information, 𝑝𝑖 , is not more than 3. Define 3 new variables 𝑝𝑖 , 𝑝𝑖 , and 𝑝𝑖
as follows:
(𝑗)

𝑝𝑖

0
if 𝑝𝑖 < 𝑗={1 otherwise.

By some calculation, when 𝑁 is the number of possible information, we have(1)∑(0.5)𝑝𝑖 = ∑ (1 − 0.5 ⋅ 𝑝𝑖𝑖(2)

− 0.25 ⋅ 𝑝𝑖

(3)

− 0.125 ⋅ 𝑝𝑖 )𝑖(1)

= 𝑁 − ∑ 0.5 ⋅ 𝑝𝑖𝑖(2)

− ∑ 0.25 ⋅ 𝑝𝑖
𝑖

𝑖
(1)

As 𝑁 does not depend on the output, minimizing (𝑁 − ∑𝑖 0.5 ⋅ 𝑝𝑖
(1)

is equivalent to minimizing (− ∑𝑖 0.5 ⋅ 𝑝𝑖(3)

− ∑ 0.125 ⋅ 𝑝𝑖 .

(2)

− ∑𝑖 0.25 ⋅ 𝑝𝑖

(2)

− ∑𝑖 0.25 ⋅ 𝑝𝑖

(3)

− ∑𝑖 0.125 ⋅ 𝑝𝑖 )(3)

− ∑𝑖 0.125 ⋅ 𝑝𝑖 ). Also, as we know that(1)minimizing – 𝑥 is equivalent to maximizing 𝑥, what we want to do is maximizing (∑𝑖 0.5 ⋅ 𝑝𝑖
∑𝑖 0.25 ⋅ 𝑝𝑖(2) + ∑𝑖 0.125 ⋅ 𝑝𝑖(3) ).

+

(𝑗)

Let 𝑤𝑖(𝑗)(𝑗)= 𝑃𝑖 for all 𝑖 and 𝑗, and let 𝑄 = {𝑝𝑖 : 𝑝𝑖

(1)= 1}. Because 𝑝𝑖 = 𝑝𝑖

(2)

+ 𝑝𝑖

(3)

+ 𝑝𝑖 ,

we have(1)(2)∑ 𝑃𝑖 ⋅ 𝑝𝑖 = ∑ 𝑃𝑖 ⋅ (𝑝𝑖
𝑖

𝑖

+ 𝑝𝑖

(3)

(1)

+ 𝑝𝑖 ) = ∑ (𝑃𝑖 ⋅ 𝑝𝑖

(2)

+ 𝑃𝑖 ⋅ 𝑝𝑖(3)+ 𝑃𝑖 ⋅ 𝑝𝑖 )

𝑖
(1)
(2)
(3)
(1)
(1)
(2)
(2)
(3)
(3)
= ∑ (𝑃𝑖 ⋅ 𝑝𝑖 + 𝑃𝑖 ⋅ 𝑝𝑖 + 𝑃𝑖 ⋅ 𝑝𝑖 ) = ∑ (𝑤𝑖 ⋅ 𝑝𝑖 + 𝑤𝑖 ⋅ 𝑝𝑖 + 𝑤𝑖 ⋅ 𝑝𝑖 )𝑖𝑖(𝑗) (𝑗)(𝑗)= ∑ 𝑤𝑖 𝑝𝑖 = ∑ 𝑤𝑖 .
(𝑗)
𝑖,𝑗
𝑝 ∈𝑄
𝑖

(1)

= 0.5, ℎ𝑖(1)+ ∑ 0.25 ⋅ 𝑝𝑖

Let ℎ𝑖(∑ 0.5 ⋅ 𝑝𝑖

(2)

(3)

= 0.25, ℎ𝑖(2)𝑖= 0.125 for all 𝑖. We have
(3)

(1)

+ ∑ 0.125 ⋅ 𝑝𝑖 ) = ∑ (ℎ𝑖𝑖𝑖(𝑗) (𝑗)(𝑗)= ∑ ℎ𝑖 𝑝𝑖 = ∑ ℎ𝑖 .
(𝑗)
𝑖,𝑗
𝑝 ∈𝑄

(1)

⋅ 𝑝𝑖

(2)

+ ℎ𝑖

(2)

⋅ 𝑝𝑖

(3)

⋅ 𝑝𝑖 )

(𝑗)

≤ 𝑊.

+ ℎ𝑖

(3)

𝑖

𝑖

Let 𝑊 = 𝑚 ⋅ ln 2. We will have the following optimization model:
Positive integer 𝑁 (number of possible information)

Input:(𝑗)

Positive real numbers 𝑤𝑖
Positive real number 𝑊

for 1 ≤ 𝑖 ≤ 𝑁 and 1 ≤ 𝑗 ≤ 3(j)Positive real number hi for 1 ≤ i ≤ N and 1 ≤ j ≤ 3hhhAssumption: w1 ≥ w2 ≥ ⋯ ≥ wn
1

2

n

(𝑗)

Output:Set 𝑄 ⊆ {𝑝𝑖 : 1 ≤ 𝑖 ≤ 𝑁 and 1 ≤ 𝑗 ≤ 3}

Constraint:∑ (𝑗)Objective Function:

Maximize ∑𝑝(𝑗) ∈𝑄 ℎ𝑖

(𝑗)

𝑝𝑖 ∈𝑄

𝑤𝑖

=𝑊
(𝑗)

𝑖

In this paragraph, we will argue that it does not mater changing the constraint to ∑𝑝(𝑗) ∈𝑄 𝑤𝑖
𝑖(𝑗)

We want to maximize ∑𝑝(𝑗) ∈𝑄 ℎ𝑖 , so we want to have elements in 𝑄 as much as possible. If
𝑖

∑ (𝑗)
𝑝𝑖

(𝑗)
(𝑗)
𝑤 < 𝑊, we may add more elements to 𝑄 to have a larger value of ∑𝑝(𝑗) ∈𝑄 ℎ𝑖 . Even we
∈𝑄 𝑖
𝑖

(𝑗)

have the constraint ∑𝑝(𝑗) ∈𝑄 𝑤𝑖𝑖(𝑗)likely to have ∑𝑝(𝑗) ∈𝑄 𝑤𝑖
𝑖

∑ (𝑗)

𝑝𝑖 ∈𝑄

(𝑗)

𝑤𝑖

(𝑗)

≤ 𝑊, it is very unlikely that we have ∑𝑝(𝑗) ∈𝑄 𝑤𝑖< 𝑊. We are𝑖(𝑗)= 𝑊 anyway. Thus, it does not matter changing ∑𝑝(𝑗) ∈𝑄 𝑤𝑖
𝑖≤ 𝑊.

By the previous paragraph, we will have the following optimization model.
Input:

Positive integer 𝑁 (number of possible information)(𝑗)Positive real numbers 𝑤𝑖
Positive real number 𝑊

for 1 ≤ 𝑖 ≤ 𝑁 and 1 ≤ 𝑗 ≤ 3= 𝑊 to(j)Positive real number hi for 1 ≤ i ≤ N and 1 ≤ j ≤ 3hhhAssumption: w1 ≥ w2 ≥ ⋯ ≥ wn
1

2

n

(𝑗)

Output:Set 𝑄 ⊆ {𝑝𝑖 : 1 ≤ 𝑖 ≤ 𝑁 and 1 ≤ 𝑗 ≤ 3}

Constraint:∑𝑝(𝑗) ∈𝑄 𝑤𝑖

(𝑗)

≤𝑊

𝑖

Objective Function:(𝑗)Maximize ∑𝑝(𝑗) ∈𝑄 ℎ𝑖
𝑖

The optimization model is exactly same as the knapsack problem. We can use the 0.5-approximation
algorithm for the knapsack problem to solve the optimization model. We can calculate all inputs of
the optimization models from the properties of the Bloom filter, and receive the best number of bits
for each information 𝑖 from the output of the models.
Exercises
Consider the following situation.
All-you-can-eat strawberry farms become much more popular, because
many students from this course decided to go there. The farm owners arevery happy about that. However, without the assumption that customers
cannot leave a strawberry partly eaten, there are a lot of partly-eaten
strawberries when they leave. After heavily discussed, the owner decided tocharge their customers for the partly-eaten strawberry. The charge will
decrease the happiness that the customer can have from those partly-eaten
strawberry. Suppose that the happiness from the remaining part of thepartly-eaten strawberry (if eaten) is 𝐻. The charge will decrease thehappiness by 𝑐 ⋅ 𝐻, when 𝑐 ≥ 0 is an integer given as an input.
In this problem, we want to eat strawberry in a way to maximize ourhappiness after being charged.
Question 1: State inputs of this problem by a mathematical formulation.
Question 2: State outputs of this problem by a mathematical formulation.
Question 3: State constraints of this problem by a mathematical formulation.
Question 4: State objective functions of this problem by a mathematical formulation.
Question 5: Write a program for solving knapsack problem based on the fact that an efficientalgorithm for solving the optimization model in Problems 1.1 – 1.4 is given in a library.
[AnswerOf1_2] YourOptimizationModel([AnswerOf1_1]);

Sets knapsack(int n, int W, int[] happiness, int[] weight){//write your code for knapsack here}

Question 6: Give an example for your optimization model such that there is some partly-eaten
strawberry in all optimal solutions.
Question 7: Suppose that there is two strawberries. The first strawberry weights 1.9998 gram, and yourhappiness from eating the strawberry is 1.9999. The second strawberry weights 2 grams, and your

happiness from eating the strawberry is 2. The charging parameter 𝑐 is 20, and you cannot each morethan 2 grams of strawberries.
What is the optimal solution and optimal value for your optimization model in this situation?
From the next question, Problem A referred to the knapsack problem for an impolite customer, where
it is possible to eat a part of strawberries without receiving any fine.
Question 8: What is an optimal solution of Problem A when the input is as given in Question 7?
Question 9: Let us consider the solution in Question 8 in the term of our optimization model. What is
the objective value of the solution for our optimization model?
Question 10: From your answer in Question 9, discuss why a 0.9-approximation algorithm for Problem
A may not be an approximation algorithm for your optimization model.
Question 11: For any specific input and output, discuss why the objective value for Problem A is nosmaller than the objective value for your optimization model.
Question 12: For any specific input, discuss why the optimal value for Problem A is no smaller than theobjective value for your optimization model.
From the next question, Problem B referred to the knapsack problem for a polite customer, where it is
not possible to eat a part of strawberries.
Question 13: For a specific output of Problem B, discuss why the objective value for Problem B is equal
to the objective value for your optimization model.
Question 14: In this lecture note, we discussed about a 0.5-approximation algorithm for Problem B. We
proved that the happiness obtained from the algorithm is at least half of the happiness obtained from
Problem A’s optimal solution.
Question 15: Discuss why the 0.5-approximation algorithm for Problem B is also a 0.5-approximation
algorithm for your optimization model.
In our discussion on the adaptive Bloom filter, for element 𝑖 that is in the cache 𝑆 withprobability 𝑃𝑖 , we randomly set 𝑘𝑖 cells of Hash table to 1. To minimize the probability of having false
positive, we optimize the following optimization problem.
Positive integer 𝑁 (number of possible information)

Input:(𝑗)

Positive real numbers 𝑤𝑖 = 𝑃𝑖 for 1 ≤ 𝑖 ≤ 𝑁 and 1 ≤ 𝑗 ≤ 3
Positive real number 𝑊 = 𝑚 ⋅ ln 2, when 𝑚 is the Hash table size
(1)

Positive real number ℎ𝑖(2)= 0.5, ℎ𝑖(3)= 0.25, ℎ𝑖= 0.125 for 1 ≤ 𝑖 ≤ 𝑁(𝑗)𝑆 ⊆ {𝑝𝑖 : 1 ≤ 𝑖 ≤ 𝑁 and 1 ≤ 𝑗 ≤ 3}

Output:(𝑗)(Elements 𝑖 will trigger at least 𝑗 bits when 𝑝𝑖
Constraint:(𝑗)∑𝑝(𝑗) ∈𝑆 𝑤𝑖

= 1.)

≤𝑊

𝑖

Objective Function:(𝑗)Maximize ∑𝑝(𝑗) ∈𝑆 ℎ𝑖𝑖(2)

We stop our discussion here, but there is still a lot of issues to consider. When 𝑝𝑖= 0 and(3)(2)
𝑝𝑖 = 1, we will not be able to find an appropriate value for 𝑘𝑖 . The output 𝑝𝑖 = 0 will be violated

(3)if 𝑘𝑖 ≥ 2, but 𝑝𝑖 = 1 will be violated when 𝑘𝑖 < 2. In the next question, we will show that thesituation will not happen if we use the greedy algorithm for the knapsack problem.
Question 16: Discuss why, when we use the 0.5-approximation algorithm for the knapsack problem to(𝑗)solve the above optimization model, we will have 𝑝𝑖(𝑗 ′ )= 1 only if 𝑝𝑖= 1 for all 𝑗 ′ < 𝑗.

Another issue from the above optimization model is: we set the maximum value of 𝑘𝑖 is no
more than 3 in the above optimization model. In reality, we might have 𝑘𝑖 much larger than 3, and what
we have from the optimization model might be far from optimal. From the next question, we will showthat assuming 𝑘𝑖 ≤ 3 is not that bad idea.
Consider the second optimization model, which have the same input, constraint, and objectivefunction, but the following output:
Output:(𝑗)𝑆 ⊆ {𝑝𝑖 : 1 ≤ 𝑖 ≤ 𝑁 and 𝑗 ≥ 1}

We will call the first problem as 𝐵𝑙𝑜𝑜𝑚3 and the second optimization problem as 𝐵𝑙𝑜𝑜𝑚∞ .
(𝑗)

Question 17: Suppose that 𝑆 ∗ is an optimal solution of 𝐵𝑙𝑜𝑜𝑚∞ , and 𝑆 ′ = {𝑝𝑖∈ 𝑆 ∗: 1 ≤ 𝑖 ≤𝑁 and 1 ≤ 𝑗 ≤ 3}. Discuss why the objective value of 𝑆 ′ is no larger than the optimal value of 𝐵𝑙𝑜𝑜𝑚3 .
Question 18: Discuss why the objective value of 𝑆 ∗ is no larger than 8/7 times of the objective value of
𝑆 ′.
Question 19: Discuss why the optimal value of 𝐵𝑙𝑜𝑜𝑚3 is no smaller than 7/8 times of the optimalvalue of 𝐵𝑙𝑜𝑜𝑚∞ .
Question 20: Discuss why a 0.5-approxiation algorithm for 𝐵𝑙𝑜𝑜𝑚3 is a 7/16-approximation algorithm
for 𝐵𝑙𝑜𝑜𝑚∞ .
Question 21: Devise a 0.5-approximation algorithm for 𝐵𝑙𝑜𝑜𝑚∞ based on the greedy algorithm for theKnapsack problem.
References[1] D. P. Williamson and D. Shmoys, “The design of approximation algorithms”, Cambridge University
Press, 2011.
[2] M. Zhong, P. Lu, K. Shen, and J. Seiferas, “Optimizing data popularity conscious bloom filters”,
Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC’08), pages
355-364.