### Why would you do it this way?

Dec. 17th, 2008 11:21 am**lederhosen**

http://www.citeulike.org/user/ima/article/3351944

"In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure..."

The article goes on to note that this is an NP-hard problem.

"In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of practical importance due to a European industry norm which requires car manufacturers to state the trunk volume according to this measure..."

The article goes on to note that this is an NP-hard problem.

## no subject

Date: 2008-12-17 01:46 am (UTC)chaos-crafter.livejournal.comTHe average drive will not attempt to sort an NP-hard problem when they go to pack their car.

The test should be - how many of these boxes can a 10 year old fit into the boot in 5 mins when offered $5 per box they fit.

## no subject

Date: 2008-12-17 01:28 pm (UTC)nefaria.livejournal.comHmm, I'm wondering what the ideal alternative measure of the volume of a trunk would involve. Trunks are generally not watertight, so filling them up with water wouldn't work. Perhaps mathematical analysis of the computer model of the trunk would do the trick.

And I'd love to see a clever mathematician come up with a trunk of say 20 cubic feet that you couldn't fit a single Rubix's cube into because of convoluted topology.

## no subject

Date: 2008-12-17 03:13 pm (UTC)sigmonster.livejournal.comAnd it's very easy to get a lower bound on the value, which is all that's required. Just stick a few boxes in, demonstrate your lower bound, and publish and advertise it as the trunk capacity. No problem.

What would be bad is if manufacturers could game the system to publish a value based on a vanishingly rare edge case. And from this point of view, having it be a hard problem is actually

better- it's an excellent law!## no subject

Date: 2008-12-18 09:36 pm (UTC)lederhosen.livejournal.comAnd it's very easy to get a lower bound on the value, which is all that's required.Maybe all that's required by the rest of the industry, but the company generally wants to get that number as high as possible. If your competitor is advertising 500L trunk space, your company is probably not going to be content with 480L when they

mightbe able to find another 30L by tinkering with it (note the reference in the article to a 'manual expert' and 'several hours of tedious work', which rather implies that the manufacturers are indeed willing to do this).There are plenty of fields where packing expertise

isa nonremovable part of the problem; it seems a shame to add it to a situation that doesn't strictlyneedit.## no subject

Date: 2008-12-18 08:19 am (UTC)lederhosen.livejournal.comGovernments mandating impossible solutions to problems because they don't understand them, very typical.The article seems to be saying that it's an industry norm rather than a government requirement, but I couldn't find a copy of the original rule to confirm that. I

canconfirm from personal experience that industry is almost as good as governments at coming up with stupid ways to do things...