Optimal Solution for Stream Merging with Receive-K
by
Adam Fuchs
I address the problem of extending the optimal off-line receive 2
algorithm proposed by Bar-Noy and Ladner to the receive 3 case. I
show that the solutions for receive 2 and receive all are special cases of
a more general algorithm. I then prove the validity of this algorithm and
show that it runs in O(n3) for n arbitrary time arrivals of clients.
Advised by Richard Ladner
MGH 228
Monday, March 3, 2003
3:30 - 4:20 pm