Dear Professor Sgall,

I'm pleased to accept

"Improved Online Algorithms for Buffer Management in QoS Switches"
by Sgall, Jiri; Chrobak, Marek; Jawor, Wojciech; Tichy, Tomas

for publication in TALG.

Please mail a completed copyright form to ACM. The form can be found at 

http://www.acm.org/pubs/copyright_form.html

If you have questions about the publication process, please contact  Marga Powell at    marga@colorado.edu
Thank you for submitting this interesting work to ACM TALG.

Sincerely,
Ron Graham


Referee: 1
Comments to the Author
I do not have any specific comments to the author.  I checked all the details of the paper and did not find any errors.  The paper is also written clearly.


Referee: 2
Comments to the Author
This paper gives the first online algorithm with a competitive ratio
below (the trivial) 2 for maximizing the total profit of unit-sized
jobs with deadlines and weights on a single machine. 
This problem is equivalent to buffer management with (variable) 
bounded delay, where the buffer size is assumed to be very large 
(so that buffer overflow does not occur).

The paper is relatively technical, but it is very well written and
the authors do an excellent job of explaining the ideas behind their
algorithms and lower bounds. The problem is relevant and I
definitely recommend acceptance. I only have a few very minor
comments that are listed below.


p.5 It is unfortunate that an "upward" charge is not the same as an
"Upward" charge. This confused me on first reading. Perhaps Upward
should be renamed Current (or whatever else you can come up with).

It could perhaps be helpful to add pictures to the description of the
charging scheme for the several cases. However, I realize that 
(EB) is difficult to draw, because the weight of job h is involved,
and you don't know when it is scheduled.

Fact 3.3 The Lemma claims 3 things, perhaps you should number them
(a),(b),(c) (i.e. split (a) into two parts).

p.7 EU-pairs, line 1: remove comma after e

p.9 l.8 replace if by whether (two times)

Update the references

p.14 l.11 verify number -> verify a number

p.15 l.-13 This comment (about lambda(xi)) is also important later,
on line 9 of p.17. Perhaps you should move it to p.12 where you
also have some other comments about lambda and delta, so that it is
more prominent. (Or refer to it when you use it the second time.)

l.-10--7 It might be helpful to add a sketch of the domain of b and c.