(Answer)
Competitive ratio is the worst performance of an on-line algorithm over optimum off-line algorithm for all possible input.
Competitive ratio = 𝑚𝑖𝑛𝑎𝑙𝑙 𝑝𝑜𝑠𝑠𝑖𝑏𝑙𝑒 𝑖𝑛𝑝𝑡𝑠(|𝑀𝑜𝑛−𝑙𝑖𝑛𝑒|/|𝑀𝑜𝑝𝑡|) |𝑀𝑜𝑛−𝑙𝑖𝑛𝑒|: the result of on-line algorithm (e.g. greedy, balance)
|𝑀𝑜𝑝𝑡|: the result of optimum off-line algorithm
(Answer)
1,2,3,4: ads / a,b,c,d: queries
Worst case matching: {(1,c), (2,d)}
Optimal case matching: {(1,a), (2,b), (3,c), (4,d)} Competitive ratio = 1/2
(Answer)
Q = {d}: the set of queries matched in Mopt but not in Mgreedy
A = {3, 4}: the set of ads linked to any node in Q. Ads in A are already matched in Mgreedy. If not, ads in A would have matched in Q.
(1) |A| ≤ |Mgreedy| (Because ads in A are already matched in Mgreedy)
(2) |Q| ≤ |A| : Otherwise, the optimal algorithm couldn’t have matched all queries in
Q, but all queries in Q were matched in Mopt.
(3) |Q| ≤ |A| ≤ |Mgreedy| : from (1) and (2)
(4) Q’ = {a,b,c} ads matched in Mopt and Mgreedy
|Mopt| = |Q| + |Q’| and | Q’| ≤|Mgreedy|
|Mopt| ≤|Q| + |Mgreedy|
Worst case is when |Q| is maximum, |Q|= |A| =|Mgreedy|
(5) |Mopt| ≤ 2|Mgreedy| |Mgreedy|/|Mopt| ≥1/2
Thus, competitive Ratio = 1/2
(Answer)
(Answer)
1. Each bucket stores time stamp & the number of 1’s
(1) time stamp: timestamp mod N = 0, 1,…, N-1 (N: window size) To store time stamp, needs 𝐥𝐨𝐠𝟐 𝑵 bits
(2) the number of 1’s: If the largest bucket size is 2𝑗, 2𝑗 ≤ 𝑁 and 𝑗 ≤ log2 𝑁 To represent j, needs 𝐥𝐨𝐠𝟐(𝐥𝐨𝐠𝟐 𝑵) bits
Each bucket requires O(log2 𝑁) since log2(log2 𝑁) ≪ log2 𝑁
2. Possible bucket size: 1, 2, 22…, 2𝑗
At most 2 buckets for each size, so there could be 2j buckets (exactly, 2(j+1) buckets).
2𝑗 ≤ 2 log2 𝑁
3. Each bucket requires O(log2 𝑁) and there could be 2j buckets (2𝑗 ≤ 2 log2 𝑁).
So totally 𝑂(log2 𝑁 × log2 𝑁) = 𝑂(log2𝑁)
The number of 1’s in the last bucket 𝑏 = 2𝑗
(1) Case 1: Estimate < actual value C
worst case: all 1’s in bucket b are within range, so estimate missed half bucket b:
1×2𝑗 =2𝑗−1 2
Minimum C: at least 1 from b + at least one of buckets of lower powers
1+2𝑗−1 +2𝑗−2 +⋯+1=1+2𝑗 −1=2𝑗 Thus, 𝐶 ≥ 2𝑗 (in fact 𝐶 ≥ 2𝑗+1 − 1), estimate missed 2𝑗−1.
Estimate is at least 50% of actual value C
(2) Case 2: Estimate > actual value C
wort case: only right most bit of b is within range and there is only one bucket of each of the sizes smaller than b
𝐶 = 1 + 2𝑗−1 + 2𝑗−2 + ⋯ + 1 = 1 + 2𝑗 − 1 = 2𝑗 𝐸𝑠𝑡𝑖𝑚𝑎𝑡𝑒 = 2𝑗−1 + 2𝑗−1 + 2𝑗−2 + ⋯ + 1 = 2𝑗−1 + 2𝑗 − 1 𝐸𝑠𝑡𝑖𝑚𝑎𝑡𝑒 − 𝐶 = 2𝑗−1 − 1
𝐸𝑠𝑡𝑖𝑚𝑎𝑡𝑒 < 3𝐶 2
So estimate is no more than 50% greater than C.