Loading...
Please wait, while we are loading the content...
Similar Documents
Average-case analysis of first fit and random fit bin packing (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Albers, Susanne Mitzenmacher, Michael |
| Description | in Proceedings of 9th ACM-SIAM Symposium on Discrete Algorithms, SIAM |
| Abstract | We prove that the First Fit bin packing algorithm is stable under the input distribution U{k − 2, k} for all k ≥ 3, settling an open question from the recent survey by Coffman, Garey, and Johnson [3]. Our proof generalizes the multi-dimensional Markov chain analysis used by Kenyon, Rabani, and Sinclair to prove that Best Fit is also stable under these distributions [11]. Our proof is motivated by an analysis of Random Fit, a new simple packing algorithm related to First Fit, that is interesting in its own right. We show that Random Fit is stable under the input distributions U{k − 2, k}, as well as present worst-case bounds and some results on distributions U{k − 1, k} and U{k, k} for Random Fit. 1 |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Multi-dimensional Markov Chain Analysis First Fit Recent Survey Open Question First Fit Bin Input Distribution Random Fit Bin Packing Random Fit Present Worst-case Bound Average-case Analysis |
| Content Type | Text |
| Resource Type | Proceeding Conference Proceedings |
