/[cvs]/ovsf/reviews.esa2007
ViewVC logotype

Contents of /ovsf/reviews.esa2007

Parent Directory Parent Directory | Revision Log Revision Log | View Revision Graph Revision Graph


Revision 1.4 - (show annotations)
Mon Jul 9 14:40:40 2007 UTC (11 years, 4 months ago) by riso
Branch: MAIN
CVS Tags: esa2007-cameraready, HEAD
Changes since 1.3: +7 -6 lines
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