home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / math / 11058 < prev    next >
Encoding:
Text File  |  1992-09-08  |  1.7 KB  |  71 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!ux1.cso.uiuc.edu!m.cs.uiuc.edu!gillies
  3. From: gillies@m.cs.uiuc.edu (Don Gillies)
  4. Subject: Re: Minimizing waste when cutting fabric.
  5. Message-ID: <1992Sep6.213343.15380@m.cs.uiuc.edu>
  6. Keywords: Waste; Fabric
  7. Organization: University of Illinois, Dept. of Comp. Sci., Urbana, IL
  8. References: <8832@amsaa-cleo.brl.mil>
  9. Date: Sun, 6 Sep 1992 21:33:43 GMT
  10. Lines: 59
  11.  
  12. The problem you are describing is known as the "2-dimensional
  13. bin-packing problem," or "stock cutting problem".  The basic
  14. assumption is that the rectangles cannot be rotated (i.e. perhaps
  15. because there is a pattern on the fabric).  Several algorithms were
  16. developed for it in the late 1970's and early 1980's, vis:
  17.  
  18. %Z     25
  19. %X A
  20. %A Daniel D. Sleator
  21. %T A 2.5 Times Optimal Algorithm for Packing in Two Dimensions
  22. %J Information Processing Letters
  23. %D 12 February 1980
  24. %V 10 1
  25. %P 37 40
  26. %K bin packing
  27. %K best
  28. %K 2-d
  29.  
  30. %Z     39
  31. %X A
  32. %A E. G. Coffman
  33. %A M. R. Garey
  34. %A D. S. Johnson
  35. %A R. E. Tarjan
  36. %T Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
  37. %J SIAM Journal on Computing
  38. %D 1980
  39. %V 9
  40. %P 808 826
  41. %K 2-d
  42. %K bin packing
  43.  
  44. %Z     141
  45. %X I
  46. %A E. G. Coffman, Jr.
  47. %A M. R. Garey
  48. %A D. S. Johnson
  49. %T Approximation Algorithms for Bin-Packing - An Updated Survey
  50. %B Algorithm Design for Computer System Design
  51. %E G. Ausiello, M. Luccertini, P. Serafini
  52. %I Springer Verlag
  53. %C Berlin
  54. %P 49 106
  55. %D 1984
  56. %K survey
  57. %K bin packing
  58.  
  59. There is also an algorithm that is asymptotically 5/4 + C times
  60. optimal (with C very large, like 11), which was published around that
  61. time in either SIAM J. on Computing or CACM, but I don't have the
  62. reference handy.
  63.  
  64. Don Gillies - gillies@cs.uiuc.edu - University of Illinois at Urbana-Champaign
  65.  
  66.  
  67. -- 
  68.  
  69.  
  70.  
  71.