Timeline for a colouring / matching problem
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2014 at 12:33 | history | bounty ended | Martin Rubey | ||
| Sep 30, 2014 at 9:11 | vote | accept | Martin Rubey | ||
| Sep 30, 2014 at 9:11 | |||||
| Sep 30, 2014 at 8:50 | vote | accept | Martin Rubey | ||
| Sep 30, 2014 at 8:50 | |||||
| Sep 29, 2014 at 19:28 | comment | added | Gerhard Paseman | Also, I am interested in just tackling the problem instance; I doubt I will come up with anything not already considered twenty or more years ago by people working on PARTITION. But perhaps you can tell me the following: by focussing on (only those boxes having) number 11, then number 11 and 13, then 11,13,12, then 11,13,12,0, it looks like the number of valid colorings is bounded above by 1, 4 , g=4*(11!)/((2!)4!5!), g*(10!)/4!. As we add more numbers, does the number of valid colorings explode or level off? Gerhard "Picking The Problem Into Pieces" Paseman, 2014.09.29 | |
| Sep 29, 2014 at 18:43 | comment | added | Gerhard Paseman | I'm thinking more about shortening: consider a coloring partly successful if it manages to color the boxes based on just the numbers 0-k for some positive integer k (or pick your favorite subset of 0-14). A short proof of infeasibility may arise from just attempting the colors 0-7. Ideally, for each coloring of the smallest boxes, toss out those colors and labels, and look for a feasible coloring of the remainder. Now shorten the vectors and see if an infeasibility proof arises from just looking at numbers 0 through 7, say. Gerhard "Merging Is Different From This" Paseman, 2014.09.29 | |
| Sep 29, 2014 at 8:19 | comment | added | Martin Rubey | Another question which I can answer: if I merge all the numbers, then I get at least several thousand possible colourings immediately. If I merge all but number 5 it seems to be much much more difficult to find a colouring - I just started the program and it didn't return so far. | |
| Sep 29, 2014 at 8:04 | comment | added | Martin Rubey | At least the second question I can answer: the numbers which occur are 0,1,...,14. 35% of the items have number 5, and 21% of the items have number 4, 12% have number 1. Do I understand correctly that you would suggest to "merge" all other numbers and hope that there are not too many colourings of this new problem? | |
| Sep 29, 2014 at 7:23 | comment | added | Martin Rubey | Unfortunately I cannot look into this right now myself - first week of teaching madness. (In case you really really want to, the code and the example are linked in the question...) Martin "A colouring would make me quite happy" Rubey :-) | |
| Sep 29, 2014 at 5:36 | comment | added | Gerhard Paseman | @Martin, how many mod 8 feasible colorings are there of the "smallest" boxes? In other words, how many ways are there of coloring the two boxes of two items and the four boxes of four items in such a way that when you are done, the remaining colors are each a multiple of 8? Also, do the "big" boxes fall into nice groups like half the boxes have numbers 1,2,3,4, 30% have numbers 6,7,8,10, and a much smaller remainder have some scattering? It may be that looking at the first six coordinates will suggest a coloring for the rest. Gerhard "Slicing Diagonally Might Also Help" Paseman, 2014.09.28 | |
| Sep 25, 2014 at 1:02 | comment | added | Gerhard Paseman | If all the colors had a multiple of 8 labels, but every feasible coloring involved coloring the 2 distinct boxes of 2 items with different colors, you would get a mod 4 or mod 8 conflict. You can look for parity conflicts this way, or assume that they have to be resolved first and thus limit the available colorings of the "smallest" 13 boxes. At the moment, I see no other easy way to find a proof of infeasibility. Gerhard "Maybe Subtract Off Symmetric Boxes" Paseman, 2014.09.24 | |
| Sep 24, 2014 at 8:13 | comment | added | Martin Rubey | Actually, I'm not all that much interested in the solution itself, but rather whether a solution exists at all. I have no idea how to find a small infeasible subset. A possibly helpful observation is that any box contains either 2 items, 4 items or 8 iteme. More precisely: there are 2 distinct boxes with 2 items, 11 distinct boxes with 4 items, the remaining boxes contain 8 items. Is there an obvious way to take advantage of this? Besides, exploiting the symmetry was a very good idea: there are 356 boxes, but only 233 distinct boxes. I adapted the program to reflect this. | |
| Sep 19, 2014 at 23:13 | comment | added | Gerhard Paseman | The above assumes there is a feasible solution you wish to find. If you want to prove that there is no feasible solution, I suspect finding a small infeasible subset of boxes is your best hope. Gerhard "Doesn't Like Infeasible So Much" Paseman, 2014.09.19 | |
| Sep 19, 2014 at 23:11 | history | answered | Gerhard Paseman | CC BY-SA 3.0 |