Show simple item record

dc.contributor.authorKleinberg, Jon M.en_US
dc.date.accessioned2007-04-23T16:29:33Z
dc.date.available2007-04-23T16:29:33Z
dc.date.issued1993-05en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR93-1350en_US
dc.identifier.urihttps://hdl.handle.net/1813/6120
dc.description.abstractWe consider the class of balancing algorithms for two servers. Such algorithms have appeared in a number of the early papers on this problem; they are so named because they seek to "balance" the distance travelled evenly among the servers. In this paper, we show a universal lower bound on the competitive ratio of any balancing algorithm for two servers. The lower bound is equal to (5 + $\sqrt{7}$)/2 ($\sim$ 3.82), and consequently shows that no optimal on-line algorithm for two servers can be expressed as a balancing algorithm.en_US
dc.format.extent555083 bytes
dc.format.extent126524 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleA Lower Bound for Two-Server Balancing Algorithmsen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics