Thumbnail
Access Restriction
Open

Author Kenyon, Claire ♦ Mitzenmacher, Michael
Source CiteSeerX
Content type Text
Publisher IEEE Computer Society Press
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Best Fit ♦ Skewed Distribution ♦ Fit Bin ♦ Set F1 ♦ Continuous Skewed Distribution ♦ Expected Asymptotic Performance Ratio ♦ Linear Waste ♦ Best Fit Bin Packing ♦ Discrete Distribution Fj Kg
Description We prove that Best Fit bin packing has linear waste on the discrete distribution U fj � kg (where items are drawn uniformly from the set f1=k � 2=3 � �j=kg) for sufficiently large k when j = k and 0:66 < 2=3. Our results extend to continuous skewed distributions, where items are drawn uniformly on [0�a], for 0:66 a < 2=3. This implies that the expected asymptotic performance ratio of Best Fit is strictly greater than 1 for these distributions.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2000-01-01
Publisher Institution IN PROCEEDINGS OF THE 41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, IEEE COMPUTER SOCIETY PRESS, LOS ALAMITOS, CA