Parent Directory | Revision Log | Revision Graph

Revision **1.4** -
(**show annotations**)

*Mon Jul 9 14:40:40 2007 UTC*
(11 years, 8 months ago)
by *riso*

Branch:**MAIN**

CVS Tags:**esa2007-cameraready, HEAD**

Changes since**1.3: +7 -6 lines**

Branch:

CVS Tags:

Changes since

Zmeny na camera-ready

1 | Todo: |

2 | |

3 | Na zvazenie: |

4 | |

5 | ? - Page 6, Line 6: 'configuration' is better than situation. |

6 | nie |

7 | |

8 | ? - Page 7, Lines 3-5: It would be better to use L, R instead of C, Z. |

9 | nie |

10 | |

11 | ? - Page 11, Lemma 3, Case 2: It is not clear how $P$ is funded, if it was |

12 | not free in $\Gamma$. It seems that a constant number of coins is not |

13 | enough, but there are available coins on recently filled places. |

14 | R: Nerozumiem celkom. Myslel Lemmu 2? Ved je to ok, nie? |

15 | nie |

16 | |

17 | ------------- |

18 | |

19 | ? - It might help the current paper if |

20 | the proof of Lemma 1 (along with the properties that lead to it) |

21 | appears in the body of the paper whereas the complexity analysis |

22 | completely appears in the appendix. |

23 | R: Ja by som to uz cele nerozsahaval... |

24 | |

25 | ?- Bottom of Page 2. The specific result of [4] should be clearly stated here. |

26 | R: Moc miesta nemame. Chceme tam nieco dodavat? |

27 | ok |

28 | |

29 | ?- Bottom of Page 3. Why is F_t+1 |

30 | defined as F_t \ v in B'? This seems to disallow reallocations |

31 | during the delete operation. Don't see why this should be the case. |

32 | ignorovat |

33 | |

34 | ?- Page 5. It would be extremely helpful to have a fairly detailed |

35 | picture that shows a complete binary tree, the thus far allocated |

36 | subtrees, and the free spaces. A later picture should be used to |

37 | illustrate properties black and white pebbles along with properties |

38 | C, P1-P3. |

39 | R: Na dalsi obrazok celkom isto miesto nie je... |

40 | ok |

41 | |

42 | ---- |

43 | |

44 | ?- I believe that the title is in some sense a misnomer, since |

45 | "bandwidth" in theoretical computer science has several technical |

46 | meanings, but the paper deals with neither of them. Maybe for |

47 | a theoretical conference some title suggesting node allocation |

48 | in binary trees might better invoke the right impression. |

49 | R: Dobry koment, premysliet do casopisu. |

50 | |

51 | Ignorovat: |

52 | |

53 | - zjednodusit analyzu. |

54 | R: :-) Aj my by sme radi... |

55 | |

56 | Done: |

57 | |

58 | - Page 3, Section 2: Either use $F$ or |

59 | $\textbf{F}$ to denote a code |

60 | assignment. |

61 | - Page 3, footnote: 'assume' instead of 'consider'. - Page 5, Line |

62 | - Page 5, Line -6: 'restrictions'. |

63 | |

64 | - Page 7, Lines 1-2: The argument seems to be incomplete. |

65 | Consider as |

66 | an example Figure 3 without the white pebbles. Now assume that a |

67 | level 0 pebble is inserted. As far as I can tell, it will be place as |

68 | the left white pebble of Figure 3, which means that it has to be white |

69 | and not black. |

70 | R: Ma pravdu. Zrusil som "black". Je tam nejaky zadrhel? |

71 | |

72 | - Page 8, Figure 5: The top half of the figure seems wrong - it |

73 | seems that $P$ should be moved one slot to the right. |

74 | |

75 | - Page 10, Lines 14-16: last three lines should be rephrased. |

76 | R: Cosi som pomenil. Je to lepsie? |

77 | |

78 | - Page 10, Line 17: 'Each request is associated with a ...' |

79 | |

80 | - General comment: use \qed at the end of proofs. |

81 | |

82 | - Speaking of both "depth" and "level" in a tree may only lead to |

83 | confusion; I'd definitely suggest to stick to only one of these terms, |

84 | and to introduce it at the very beginning. |

85 | R: Zmenil som depth na level. |

86 | |

87 | - I'm probably missing something basic, but I didn't understand Fig. 2. |

88 | Why can't the rightmost vertex of level 2 be allocated? |

89 | R: Ma tam byt level. |

90 | |

91 | - remove appendix, reference technical report on Arxiv |

92 | |

93 | -------------------- review 1 -------------------- |

94 | |

95 | |

96 | his paper studies the following resource allocation problem. We |

97 | are given a complete binary tree of height $n$, where the root is in |

98 | level $n$ and the leaves are in level 0. There are two kinds of |

99 | requests. An insertion request for a subtree of height $k$ is served |

100 | by assigning a vertex of height $k$ to the request, such that at any |

101 | given time every path from a leaf to the root must contain at most |

102 | one assigned vertex. A deletion request frees the appropriate |

103 | vertex. Observe that in order to serve an insertion request, we may |

104 | need to move some allocated subtrees. The authors present an |

105 | algorithm whose amortized complexity is $O(1)$ reallocations per |

106 | request. |

107 | |

108 | I didn't go over the Appendix, but the main part of the paper is |

109 | well written. I especially liked the interval representation of the |

110 | problem. |

111 | |

112 | Overall, I think it's a good paper with an interesting application. |

113 | |

114 | Specific comments: |

115 | - Page 3, Section 2: Either use $F$ or |

116 | $\textbf{F}$ to denote a code |

117 | assignment. |

118 | - Page 3, footnote: 'assume' instead of 'consider'. |

119 | - Page 5, Line -6: 'restrictions'. |

120 | - Page 6, Line 6: 'configuration' is better than situation. |

121 | - Page 7, Lines 1-2: The argument seems to be incomplete. |

122 | Consider as |

123 | an example Figure 3 without the white pebbles. Now assume that a |

124 | level 0 pebble is inserted. As far as I can tell, it will be place as |

125 | the left white pebble of Figure 3, which means that it has to be white |

126 | and not black. |

127 | - Page 7, Lines 3-5: It would be better to use L, R instead of C, Z. |

128 | - Page 8, Figure 5: The top half of the figure seems wrong - it |

129 | seems |

130 | that $P$ should be moved one slot to the right. |

131 | - Page 10, Lines 14-16: last three lines should be rephrased. |

132 | - Page 10, Line 17: 'Each request is associated with a ...' |

133 | - Page 14, Lemma 7: The statement is unclear - what are 'there free |

134 | places'? |

135 | - General comment: use \qed at the end of proofs. |

136 | |

137 | |

138 | -------------------- review 2 -------------------- |

139 | |

140 | |

141 | This paper is really a data structures paper in disguise (related to binary |

142 | budy system in memory allocation). The problem is to assign Orthogonal |

143 | Variable Spreading Factor (OVSF) codes to users over time. Codes may be |

144 | requested and then released. |

145 | |

146 | The authors represent the codes using a complete binary tree. They use a |

147 | pebble system to mark which codes are given and which are free. They give a |

148 | fairly clever online solution to compute a solution that reallocates codes |

149 | with O(1) reallocations per request (insert: request for new code, delete: |

150 | giving up a code). This is a significant improvement over the previous |

151 | results. Previous best result was O(h), the height of the binary tree. |

152 | |

153 | |

154 | -------------------- review 3 -------------------- |

155 | |

156 | |

157 | The paper presents an online approximation algorithm for a resource |

158 | allocation problem motivated by a problem in wireless networking. We |

159 | are given a complete binary tree of height n and a sequence of |

160 | insert and delete requests. The insert request asks for a complete |

161 | subtree of a given height whereas the delete request frees a |

162 | previously allocated subtree. In order to serve an insert request, |

163 | it may be necessary to reallocate some earlier requests so as to |

164 | free up a large enough subtree. The performance of the online |

165 | algorithm is measured by the number of reallocations it performs, |

166 | amortized over all requests. The paper presents an algorithm that |

167 | performs O(1) reallocations per request, on average. The problem is |

168 | quite interesting both from the point of view of applications and |

169 | from a theoretical point of view. The result in the paper, an |

170 | O(1)-competitive online algorithm, is a significant improvement over |

171 | the best known previous result due to Erlebach et. al (citation |

172 | [4]), who present a \theta(n)-competitive online algorithm. The |

173 | algorithm is simple and the invariant it satisfies (described as |

174 | properties C, P1- P3) is easy to understand. The algorithm is also |

175 | deterministic and the overall result is quite satisfying. While the |

176 | algorithm is simple, the analysis is quite involved and it would be |

177 | a nice improvement to the paper if the analysis were simplified. For |

178 | example, a key starting point of the analysis is stated in Lemma 1. |

179 | This lemma essentially says that if the current allocation satisfies |

180 | properties C, P1-P3 and if there is enough total free space to |

181 | satisfy an insert request, then there is a large enough subtree to |

182 | satisfy the request. This lemma takes 3.5 pages to prove and its |

183 | proof appears in the appendix. I read this part of the appendix just |

184 | because I wanted to understand Lemma 1. However, I did not read the |

185 | rest of the appendix and don't have a precise understanding of the |

186 | complexity analysis in Section 4. It might help the current paper if |

187 | the proof of Lemma 1 (along with the properties that lead to it) |

188 | appears in the body of the paper whereas the complexity analysis |

189 | completely appears in the appendix. |

190 | |

191 | A few specific comments. Bottom of Page 2. The specific result of |

192 | [4] should be clearly stated here. Bottom of Page 3. Why is F_t+1 |

193 | defined as F_t \ v in B'? This seems to disallow reallocations |

194 | during the delete operation. Don't see why this should be the case. |

195 | Page 5. It would be extremely helpful to have a fairly detailed |

196 | picture that shows a complete binary tree, the thus far allocated |

197 | subtrees, and the free spaces. A later picture should be used to |

198 | illustrate properties black and white pebbles along with properties |

199 | C, P1-P3. |

200 | |

201 | |

202 | -------------------- review 4 -------------------- |

203 | |

204 | |

205 | This paper is more or less a classical data structuring work |

206 | about a certain way of dynamically allocating nodes in a complete binary |

207 | tree. |

208 | It has a quite convincing practical motivation, being connected |

209 | to protocols actually used in contemporary cell phone networks. |

210 | The solution resembles in some respect the red-black trees of Tarjan |

211 | (although it speaks about black and white pebbles). The algorithm |

212 | has a clean main idea and reasonably simple invariant, while the |

213 | update procedures are more complicated and the proof is an extensive |

214 | case analysis. |

215 | COMMENTS FOR AUTHORS: |

216 | I believe that the title is in some sense a misnomer, since |

217 | "bandwidth" in theoretical computer science has several technical |

218 | meanings, but the paper deals with neither of them. Maybe for |

219 | a theoretical conference some title suggesting node allocation |

220 | in binary trees might better invoke the right impression. |

221 | |

222 | Speaking of both "depth" and "level" in a tree may only lead to |

223 | confusion; I'd definitely suggest to stick to only one of these terms, |

224 | and to introduce it at the very beginning. |

225 | |

226 | I'm probably missing something basic, but I didn't understand Fig. 2. |

227 | Why can't the rightmost vertex of level 2 be allocated? |

228 |

CVS Admin">CVS Admin | ViewVC Help |

Powered by ViewVC 1.1.26 |