<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Finding Space -->
<!--X-From-R13: @rq Zbiryl <awyN#SRE,BZOQS.ADU> -->
<!--X-Date: Sat, 16 Aug 1997 09:03:51 +0000 -->
<!--X-Message-Id: 199708160910.FAA17002#NEDS,PLACE.ORG -->
<!--X-Content-Type: text -->
<!--X-Reference: 9708160230.8c3o@ami-cg.GraySage.Edmonton.AB.CA -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Finding Space</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:njl#NEDS,PLACE.ORG">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00619.html">Previous</a>
| <a href="msg00621.html">Next</a>
]
Thread:
[ <a href="msg00619.html">Previous</a>
| <a href="msg00625.html">Next</a>
]
Index:
[ <A HREF="author.html#00620">Author</A>
| <A HREF="#00620">Date</A>
| <A HREF="thread.html#00620">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Finding Space</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI>
<LI><em>Subject</em>: Re: [MUD-Dev] Finding Space</LI>
<LI><em>From</em>: Ned Lovely <<A HREF="mailto:njl#NEDS,PLACE.ORG">njl#NEDS,PLACE.ORG</A>></LI>
<LI><em>Date</em>: Sat, 16 Aug 1997 05:10:36 -0400 (EDT)</LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
> :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
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="00619" HREF="msg00619.html">Re: [MUD-Dev] Finding Space</A></STRONG>
<UL><LI><EM>From:</EM> cg#ami-cg,GraySage.Edmonton.AB.CA (Chris Gray)</LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00619.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00621.html">Re: [MUD-Dev] C&C and Event Rescheduling</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00619.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00625.html">Re: [MUD-Dev] Finding Space</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00620"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00620"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>Re: [MUD-Dev] PK again (was: Character evolution)</STRONG>, <EM>(continued)</EM>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<ul compact>
<LI><strong><A NAME="01337" HREF="msg01337.html">Re: [MUD-Dev] PK again (was: Character evolution)</A></strong>,
Jon A. Lambert <a href="mailto:jlsysinc#ix,netcom.com">jlsysinc#ix,netcom.com</a>, Sun 21 Sep 1997, 08:24 GMT
</LI>
</ul>
</ul>
</ul>
</ul>
</ul>
</ul>
</ul>
</LI>
<LI><strong><A NAME="00623" HREF="msg00623.html">OT: test</A></strong>,
Odysseus Laertes <a href="mailto:jlsysinc#ix16,ix.netcom.com">jlsysinc#ix16,ix.netcom.com</a>, Sat 16 Aug 1997, 19:19 GMT
<UL>
<li><Possible follow-up(s)><br>
<LI><strong><A NAME="00628" HREF="msg00628.html">OT: test</A></strong>,
Jon A. Lambert <a href="mailto:jlsysinc#ix14,ix.netcom.com">jlsysinc#ix14,ix.netcom.com</a>, Sun 17 Aug 1997, 05:42 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00619" HREF="msg00619.html">Re: [MUD-Dev] Finding Space</A></strong>,
Chris Gray <a href="mailto:cg#ami-cg,GraySage.Edmonton.AB.CA">cg#ami-cg,GraySage.Edmonton.AB.CA</a>, Sat 16 Aug 1997, 06:05 GMT
<UL>
<LI><strong><A NAME="00620" HREF="msg00620.html">Re: [MUD-Dev] Finding Space</A></strong>,
Ned Lovely <a href="mailto:njl#NEDS,PLACE.ORG">njl#NEDS,PLACE.ORG</a>, Sat 16 Aug 1997, 09:03 GMT
</LI>
<LI><strong><A NAME="00625" HREF="msg00625.html">Re: [MUD-Dev] Finding Space</A></strong>,
Ned Lovely <a href="mailto:njl#NEDS,PLACE.ORG">njl#NEDS,PLACE.ORG</a>, Sat 16 Aug 1997, 20:53 GMT
</LI>
</UL>
</LI>
<LI><strong><A NAME="00603" HREF="msg00603.html">Finding Space</A></strong>,
Michael Hohensee <a href="mailto:michael#sparta,mainstream.net">michael#sparta,mainstream.net</a>, Fri 15 Aug 1997, 14:03 GMT
<UL>
<LI><strong><A NAME="00607" HREF="msg00607.html">Re: [MUD-Dev] Finding Space</A></strong>,
Shawn Halpenny <a href="mailto:malachai#iname,com">malachai#iname,com</a>, Fri 15 Aug 1997, 18:12 GMT
<UL>
<LI><strong><A NAME="00654" HREF="msg00654.html">Re: [MUD-Dev] Finding Space</A></strong>,
Nathan Yospe <a href="mailto:yospe#hawaii,edu">yospe#hawaii,edu</a>, Mon 18 Aug 1997, 08:01 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>