Re: A Tailor's Problem

Article View: sci.math.num-analysis

Article #400

Back to sci.math.num-analysis Previous Next

#400

From: Eli Chiprout
Date: Tue, 01 Sep 1992 18:21

13 lines
969 bytes

In <1992Sep1.190730.1@vmsa.technion.ac.il> chr09tk@vmsa.technion.ac.il writes:
>We are given a roll of cloth of a given width and unlimited length. We are also
>given a finite set of polygons (pieces of clothing). We want to cut out the
>polygons using a minimal length of the cloth. Devise an algorithm that will get
>us as close as possible to the minimum (within reasonable time). 

Sounds like the travelling salesman again -- NP complete at best.

--
Eli Chiprout
Dept. of Electronics, Carleton University
Ottawa, Ontario, Canada
emc@doe.carleton.ca

Technical Details

Message-ID: <emc.715371702@uhura>

Path: arc1-ca.pugleaf.net!sparky!uunet!utcsri!torn!cunews!emc

References: <1992Sep1.190730.1@vmsa.technion.ac.il>

Show Full Headers

Complete Article Headers

Newsgroups: sci.math.num-analysis
Path: arc1-ca.pugleaf.net!sparky!uunet!utcsri!torn!cunews!emc
From: emc@doe.carleton.ca (Eli Chiprout)
Subject: Re: A Tailor's Problem
Message-ID: <emc.715371702@uhura>
Sender: news@cunews.carleton.ca (News Administrator)
Organization: Dept. of Electronics, Carleton University
References: <1992Sep1.190730.1@vmsa.technion.ac.il>
Date: Tue, 1 Sep 1992 18:21:42 GMT
Lines: 13

Reply to Parent Message