home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / sci / math / numanal / 2611 < prev    next >
Encoding:
Text File  |  1992-09-01  |  945 b   |  25 lines
  1. Newsgroups: sci.math.num-analysis
  2. Path: sparky!uunet!utcsri!torn!cunews!emc
  3. From: emc@doe.carleton.ca (Eli Chiprout)
  4. Subject: Re: A Tailor's Problem
  5. Message-ID: <emc.715371702@uhura>
  6. Sender: news@cunews.carleton.ca (News Administrator)
  7. Organization: Dept. of Electronics, Carleton University
  8. References: <1992Sep1.190730.1@vmsa.technion.ac.il>
  9. Date: Tue, 1 Sep 1992 18:21:42 GMT
  10. Lines: 13
  11.  
  12. In <1992Sep1.190730.1@vmsa.technion.ac.il> chr09tk@vmsa.technion.ac.il writes:
  13. >We are given a roll of cloth of a given width and unlimited length. We are also
  14. >given a finite set of polygons (pieces of clothing). We want to cut out the
  15. >polygons using a minimal length of the cloth. Devise an algorithm that will get
  16. >us as close as possible to the minimum (within reasonable time). 
  17.  
  18. Sounds like the travelling salesman again -- NP complete at best.
  19.  
  20. --
  21. Eli Chiprout
  22. Dept. of Electronics, Carleton University
  23. Ottawa, Ontario, Canada
  24. emc@doe.carleton.ca
  25.