Bin packing part 3: Need for speed

re: Bin packing part 3: Need for speed

Joe Celko — Sun, 13 Jan 2008 17:41:55 GMT

Did you ever see some of the solutions for Codd's t-join problem? It is a "best fit" situation -- given classrooms wtih various numbers of seat5s and classes with various numbers of students, how do you assign rooms to classes with the least wasted space?

re: Bin packing part 3: Need for speed

Hugo Kornelis — Mon, 14 Jan 2008 08:26:00 GMT

Hi Joe,

You mean those covered in your "SQL for smarties"? I checked those out when I tried to answer the usenet post that ultimately resulted in this series of blog post, but they didn't fit the problem - the solutions given in your book all relied on each classroom having a different size, and each class having a different number of students. Allso, none of those solution considered combining two classes in a single class room. (Which makes sense if you are teaching, but changes the problem from bin packing to best fit - a completely different problem, requiring a completely different solution).

In part 5 of this series, I'll present an updated version of the code I originally posted in answer to said usenet post, which is MUCH faster than any of the other alternatives, and yields very acceptable packing efficiency. This code does utiilize a best fit strategy as part of the algorithm. You must be familiar with it, since I once sent you a copy when you asked for material for the third (?) edition of "Smarties", but you ultimately chose not to include it. That's why I'm now writing this series.

Best, Hugo

Bin packing part 4: The set-based disaster

SELECT Hints, Tips, Tricks FROM Hugo Kornelis WHERE RDBMS = 'SQL Server' — Sun, 26 Oct 2008 23:30:46 GMT

Almost a year ago now, I started a series of blog post on the bin packing problem . But after the first

Bin packing part 5: Set-based iteration

SELECT Hints, Tips, Tricks FROM Hugo Kornelis WHERE RDBMS = 'SQL Server' — Mon, 17 Oct 2011 22:11:51 GMT

One of the most common techniques authors use to keep their readers interested is to leave them with