From: Matthew Skala <mskala_at_cs.toronto.edu>

Date: Sun, 21 Mar 2010 12:46:38 -0400 (EDT)

Date: Sun, 21 Mar 2010 12:46:38 -0400 (EDT)

On Sun, 21 Mar 2010, Joachim Schimpf wrote: > problem it solves has 15 boxes, so there is plenty of room > for improvement: different models, other constraints, other > solvers, heuristics, maybe there is even an efficient > algorithm for the problem? Can there be duplicate boxes, and if so can a box be placed on top of an identical box? I think that the problem as stated excludes duplicate boxes because it says "different sizes"; and the use of "greater than or equal" in the rules for stacking seems to suggest that if there were two identical boxes, then one could stack on top of the other. In either of those cases (no duplicates, or duplicates may be placed on each other) then *except for the restriction of 12 boxes per stack*, this is the minimal chain decomposition problem, for which an efficient algorithm is given in the paper below. A group I work with at the University of Waterloo recently published a paper that I presented at ISAAC'09 (and even more recently, we submitted the journal version) and that drew heavily on the Supowit paper, so it's fresh in my mind. @article{Supowit:Decomposing, author = "Kenneth J. Supowit", title = "Decomposing a Set of Points into Chains, with Applications to Permutation and Circle Graphs", journal = "Information Processing Letters", volume = "21", number = "5", year = "1985", pages = "249--252", bibsource = "DBLP, http://dblp.uni-trier.de", } I don't know what the consequences of the limit on total chain length may be. Nonetheless, the Supowit algorithm might provide a good starting point for clever heuristics. At the very least, if you run the Supowit algorithm and the result happens to have all chains of length 12 or less, then you know you're done. If people need help obtaining the Supowit paper, they should contact me off-list. (Why reveal this information to possible "opponents"? It'll make for a more interesting race if we all run from the same starting line!) -- Matthew Skala, postdoctoral researcher, Universities of Toronto and Waterloo mskala_at_cs.toronto.edu mskala_at_cs.uwaterloo.ca mskala_at_ansuz.sooke.bc.caReceived on Sun Mar 21 2010 - 16:44:05 CET

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*