Michael A. Bender
Abstract
The sum-of-squares algorithm (SS) was introduced by Csirik, Johnson, Kenyon, Shor, and Weber for online bin packing of integral-sized items into integral-sized bins. First, we show the results of experiments from two new variants of the SS algorithm. The first variant, which runs in time O(n√BlogB), appears to have almost identical expected waste as the sum-of-squares algorithm on all the distributions mentioned in the original papers on this topic. The other variant, which runs in O(nlogB) time, performs well on most, but not on all of those distributions. We also apply SS to the online memory-allocation problem. Our experimental comparisons between SS and Best Fit indicate that neither algorithm is consistently better than the other. If the amount of randomness in item sizes is low, SS appears to have lower waste than Best Fit, whereas, if the amount of randomness is high Best Fit appears to have lower waste than SS. Our experiments suggest that in both real and synthetic traces, SS does not seem to have an asymptotic advantage over Best Fit, in contrast with the bin-packing problem.
- Berger, E. D., McKinley, K. S., Blumofe, R. D., and Wilson, P. R. 2000. Hoard: a scalable memory allocator for multithreaded applications. SIGPLAN Not. 35, 11, 117--128. Google Scholar
Digital Library
- Berger, E. D., Zorn, B. G., and McKinley, K. S. 2002. Reconsidering custom memory allocation. In OOPSLA '02: Proceedings of the 17th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications. ACM Press, New York. 1--12. Google ScholarDigital Library
- Coffman, E.G., Courcoubetis, C., Garey, M. R., Johnson, D. S., McGeogh, L. A., Shor, P. W., Weber, R. R., and Yannakakis, M. 1991. Fundamental discrepancies between average-case analyses under discrete and continuous distributions. In Proceedings of the 23rd Annual Symposium on Theory of Computing. 230--240.Google Scholar
- Coffman, E. G., Garey, M. R., and Johnson, D. S. 1996. Approximation Algorithm for NP-Hard Problems, Approximation Algorithms for Bin Packing: A Survey. 46--93. Google ScholarDigital Library
- Coffman, E. G., Courcoubetis, C., Garey, M. R., Johnson, D. S., Shor, P. W., Weber, R. R., and Yannakakis, M. 2000. Bin packing with discrete item sizes, part I: Perfect packing theorems and average case behavior of optimal packings. SIAM Journal on Discrete Math. 13, 384--402. Google ScholarDigital Library
- Coffman, E. G. Jr. and Leung, J. Y. 1977. Combinatorial analysis of an efficient algorithm for processor and storage allocation. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science. 214--221.Google Scholar
- Coffman, E. G. Jr. and Leighton, F. T. 1986. A provably efficient algorithm for dynamic storage allocation. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing. 77--90.Google Scholar
- Coffman, E. G., Jr. Johnson, D. S., Shor, P. W., and Weber, R. R. 1993. Markov chains, computer proofs, and average-case analysis of best fit bin packing. In STOC'93: Proceedings of the 25th Annual ACM Symposium on Theory of Computing. ACM Press, New York. 412--421.Google Scholar
- Coffman, E. G. Jr., Johnson, D. S., Shor, P. W., and Weber, R. R. 1997. Bin packing with discrete item sizes, part ii: Tight bounds on first fit. Random Structures and Algorithms 10, 1--2, 69--101. Google ScholarDigital Library
- Csirik, J., Johnson, D. S., Kenyon, C., Shor, P. W., and Weber, R. R. 1999. A self organizing bin packing heuristic. In Proceedings of ALENEX Workshop. 246--265. Google ScholarDigital Library
- Csirik, J., Johnson, D. S., Kenyon, C., Orlin, J., Shor, P. W., and Weber, R. R. 2000. On the sum-of-squares algorithm for bin packing. In Proceedings of the 32nd Annual ACM Symp. on the Theory of Computing. 208--217. Google ScholarDigital Library
- Csirik, J., Johnson, D. S., Kenyon, C., Orlin, J. B., Shor, P. W., and Weber, R. R. 2006. On the sum-of-squares algorithm for bin packing. J. ACM 53, 1, 1--65. Google ScholarDigital Library
- Dyckhoff, H. 1990. A typology of cutting and packing problem sacking. European Journal of Operational Research 44, 145--159.Google ScholarCross Ref
- Garey, M. R. and Johnson, D. S. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. New York, NY, USA.Google Scholar
- Horowitz, E., Mehta, D., and Sahni, S. 2006. Fundamentals of Data Structures in C++. W. D. Freeman, San Fransisco, CA. Google ScholarDigital Library
- Johnstone, M. S. 1997. Non-Compacting Memory Allocation and Real-Time Garbage Collection. PhD thesis. Google ScholarDigital Library
- Johnstone, M. S. and Wilson, P. R. 1998. The memory fragmentation problem: solved? In ISMM'98: Proceedings of the 1st International Symposium on Memory Management. ACM Press, New York. 26--36. Google ScholarDigital Library
- Kenyon, C. and Mitzenmacher, M. 2002. Linear waste of best fit bin packing on skewed distributions. Random Struct. Algorithms 20, 3, 441--464. Google ScholarDigital Library
- Lea, D. A memory allocator. http://g.oswego.edu/dl/html/malloc.html.Google Scholar
- Luby, M. G., Naor, J., and Orda, A. 1996. Tight bounds for dynamic storage allocation. SIAM Journal on Discrete Math. 9, 155--1660. Google ScholarDigital Library
- Robson, J. M. 1974. Bounds for some functions concerning dynamic storage allocation. Journal of the ACM 12, 491--499.Google ScholarDigital Library
- Wilson, P. R., Johnstone, M. S., Neely, M., and Boles, D. 1995. Dynamic storage allocation: A survey and critical review. In Proc. Int. Workshop on Memory Management, Kinross Scotland (UK). Google ScholarDigital Library
- Zorn, B. and Grunwald, D. 1994. Evaluating models of memory allocation. ACM Trans. Model. Comput. Simul. 4, 1, 107--131.Google ScholarDigital Library
Recommendations
Efficient models for timetable information in public transportation systems
We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the time-expanded approach, every event at a station, e.g., the departure of a train, is modeled as a node in ...
Comments