home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / theory / 2417 < prev    next >
Encoding:
Internet Message Format  |  1992-11-14  |  1.1 KB
  1. Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!cs.utexas.edu!ut-emx!tivoli!foraker!taylor
  2. From: taylor@tivoli.com (Eric Taylor)
  3. Newsgroups: comp.theory
  4. Subject: Is this an Np-Complete Problem
  5. Message-ID: <6097@tivoli.UUCP>
  6. Date: 14 Nov 92 03:29:57 GMT
  7. Sender: news@tivoli.UUCP
  8. Lines: 19
  9.  
  10. This is a fairly practical problem but is probably
  11. a good exercise:
  12.  
  13. Suppose I have "n" rectangles of varying width.
  14. I want to fit them into another rectangle of constant
  15. width called "W" and infinite height.
  16. I want to lay these rectangles into a matrix in
  17. Row-Major order where the difference between the
  18. total width of the columns and "W" is at a non-positive minimum.
  19. The rectangles will form columns (you can't just pack
  20. rectangles in until they don't fit).
  21.  
  22. Is there a polynomial solution to this problem?
  23. If you pick a number "c" for the
  24. number of columns, it is concievable that a larger
  25. value of "c" could result in a smaller width.
  26. Am I wrong in this assumption?  If I am wrong
  27. then a simple binary search for the optimal "c" will
  28. work.  (n log n for the total problem).
  29.