[MUD-Dev] Finding Space

[Ned Lovely]

> :A friend of mine glanced at this problem and said, "Oh, that's a
> :bin-stuffing problem."  Of course, he didn't remember anything else
> :about the problem, so here I am. :)
> Also called "bin packing", I believe. Not something I know anything about.

Hrm... Bin packing is mentioned in "Introduction to Algorithms" by Cormen,
Leiserson, and Rivest. MIT Press, 1990. It's a nice book to have on the
shelf...

At any rate, one of the problems in the chapter on approximation algorithms
is where it comes up. I'll use () for subscripts.

37-1 Bin packing
Suppose that we are given a set of n objects, where the size s(i) of the ith
object satisfies 0 < s(i) < 1. We wish to pack all the objects into the
minimum numver of unit-sized bins. Each bin can hold any subset of the objects
whose total size does not exceed 1.

a. Prove that the problem of determining the minimum number of bins required
is NP-hard. (Hint: Reduce from the subset-sum problem.)

The first-fit heuristic takes each object in turn and places it into
the first bin that can accomodate it. Let S = (the sum from i = 1 to n for
each S(i)). 

b. Argue that the optimal number of bins required is at least ceiling(S).

c. Argue that teh first-fit heuristic leaves at most one bin less than half
full.

d. Prove that the numver of bins used by the first-fit heuristic is never
more than ceiling(2S).

e. Prove a ration bound of 2 for the first fit heuristic.

f. Give an efficient implementation of the first fit heuristic, and analyze
it's running time.

> :Does anyone have the answer? :)
> Well, this is beginning to sound a *lot* like Winograd's "Blocks World".
> He got a PhD degree for implementing that!

Do you have a good URL? I found some interesting looking stuff, but nothing
that was all that good...

Well, seeing as this is my first mail, I should introduce myself :).

My involvement with muds started when a local 8-line BBS ran a copy of
circlemud... I've always been fascinated with people creating their own
stories, and muds seem like the ideal forum for that.

Right now, I'm trying to find somebody to hand me a well-designed mud that
I can just implement. I know I can code, and I've got lots of theory on
design, so I figure I should give it all a whirl.

Happy to be aboard :)

--
njl