Random-order bin packing |
| |
| Authors: | Edward G Coffman Jr Jnos Csirik Lajos Rnyai Ambrus Zsbn |
| |
| Institution: | aDepartment of Electrical Engineering, Columbia University, 1312 S.W. Mudd, 500 West 120th Street, New York, NY 10027, USA;bDepartment of Computer Science, University of Szeged, Árpád tér 2, H-6720 Szeged, Hungary;cMTA SZTAKI, Kende u. 13-17, Budapest, Hungary;dDepartment of Algebra, Budapest University of Technology and Economics, Budapest, Hungary |
| |
| Abstract: | The average-case analysis of algorithms usually assumes independent, identical distributions for the inputs. In C. Kenyon, Best-fit bin-packing with random order, in: Proc. of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 1996, pp. 359–364] Kenyon introduced the random-order ratio, a new average-case performance metric for bin packing heuristics, and gave upper and lower bounds for it for the Best Fit heuristics. We introduce an alternative definition of the random-order ratio and show that the two definitions give the same result for Next Fit. We also show that the random-order ratio of Next Fit equals to its asymptotic worst-case, i.e., it is 2. |
| |
| Keywords: | Bin packing Worst-case analysis |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
