# Contents of /ovsf/reviews.esa2007

Revision 1.4 - (show annotations)
Mon Jul 9 14:40:40 2007 UTC (11 years, 8 months ago) by riso
Branch: MAIN
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