Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A maiden analysis of longest wait first

A maiden analysis of longest wait first We consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. The algorithm Longest Wait First (LWF) always services the page where the aggregate waiting times of the outstanding requests for that page is maximized. We provide the first non-trivial analysis of the worst case performance of LWF. On the negative side, we show that LWF is not s -speed O (1)-competitive for s < 1+&sqrt;5/2. On the positive side, we show that LWF is 6-speed O (1)-competitive. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

A maiden analysis of longest wait first

Download PDF
19 pages

Loading next page...
 
/lp/association-for-computing-machinery/a-maiden-analysis-of-longest-wait-first-5wtcVdjTJV
Publisher
Association for Computing Machinery
Copyright
Copyright © 2005 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1077464.1077467
Publisher site
See Article on Publisher Site

Abstract

We consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. The algorithm Longest Wait First (LWF) always services the page where the aggregate waiting times of the outstanding requests for that page is maximized. We provide the first non-trivial analysis of the worst case performance of LWF. On the negative side, we show that LWF is not s -speed O (1)-competitive for s < 1+&sqrt;5/2. On the positive side, we show that LWF is 6-speed O (1)-competitive.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Jul 1, 2005

There are no references for this article.