Dear Jiri Sgall

Dear Fabrizo Grandoni

I am writing regarding your submission to the Journal of Discrete 
Algorithms, 'Online competitive algorithms for maximizing weighted 
throughput of unit jobs',  JDA 04-62.

I am attaching two referee reports that we have received on your paper 
which the editors have considered. I am pleased to say your paper has 
been accepted, subject to the modifications suggested by the referee.

Please send us a .pdf and electronic source file of the revised paper 
which we will forward to Elsevier who will prepare it for publication.

Sincerely,

Jane Spurr

====================

Paper#:  4-62

Title:   Online Competitive Algorithms 
         for Maximizing Weighted Throughput of Unit Jobs


An online buffer management problem that arises in networks supporting
Quality-of-Service (QoS) applications is considered. Packets with
different QoS values arrive at a network switch and are to be sent
along an outgoing link. Due to overloading conditions, some packets
have to be dropped. The objective is to maximize the total value of
packets that are sent. This is modeled as an online unit-job
scheduling problem, where each job is specified by its release time,
deadline, and a non-negative weight (QoS value). The goal is to
maximize the weighted throughput, that is the total weight of
scheduled jobs.

They present several competitive online algorithms for various
versions of this problem, as well as some lower bounds on the
competitive ratio. The most interesting result is the randomized
algorithm RMIX with competitive ratio e/(e-1) = 1.582. This algorithm
and its analysis is simple and elegant. However, it is based on known
techniques. The best known previous result is a deterministic
algorithm in [1] with competitive ratio 1.94. In the randomized case,
the best known lower bound on the competitive ratio is 1.25.  In
addition, they present a de-randomized version of RMIX. For this
deterministic version a more general model is needed. In detail, the
outgoing link has bandwidth m, i.e., it can send m packets at a
time. In this case, the de-randomized deterministic algorithm achieves
a competitive ratio of 1/(1-(m/(m+1))^m). When m \to \infty, the
competitive ratio tends to e/(e-1).

The remaining part of the paper deals with special cases of the
problem.  First, they consider s-bounded instances, where the span of
each job (deadline minus release time) is at most s. For 2-bounded
instances, they give a randomized algorithm with competitive ratio
1.25, matching a known lower bound. The algorithm is simple, but its
analysis is technical and uses standard techniques. In addition, they
present a deterministic algorithm which can be seen as a deterministic
version of RMIX. For 3-bounded instances, this algorithm achieves a
competitive ratio of \phi = 1.618, matching a known lower bound. In
general, for s-bounded instances, the algorithm achieves a competitive
ratio of 2-2/s+o(1/s). Again, the algorithm is simple, but its
analysis - in particular in the general case - is technical and uses
standard techniques. Finally, they present lower bounds on the
competitive ratio for s-uniform instances, where the span of each job
is exactly s. For randomized algorithms, they prove a lower bound that
is increasing with s from 4-2\sqrt{2} = 1.172, for s = 2, to 1.25, for
large s.  In the deterministic case, they prove a lower bound of
\sqrt{2} = 1.414 on memoryless algorithms for 2-uniform instances.

The paper is very well written and it is easy to read (see the
following very short list for improvements).
- Page 9: I would suggest a colon at the end of line 6 and 
          no period at the end of line 7 and 8.
- Page 9, algorithm EDF: Remark that h is the heaviest pending job.
- Page 12, line 5: Since j is scheduled by EDF in E ...
- Page 19: Reference [13] is incomplete.

I think the studied model is very interesting. One one hand it is
simple and clear and on the other hand it has applications in networks
supporting QoS applications. The presented results are solid, but
there is no general result matching a lower bound. Most of the used
techniques are standard. I would vote for a weak acceptation of this
paper as it is.  But I would recommend to incorporate the results of
paper [1] (the authors of paper [1] are a subset of this paper) in
this paper. Then, a complete overview on current results in this topic
would be given and I would recommend an acceptation.

References

[1] M. Chrobak, W. Jawor, J. Sgall, and T. Tichy. 
    Improved online algorithms for buffer management in QoS switches. 
    In Proc. of the 12th ESA, 2004.

====================