Alternate configurations of SWO

We note that, as with the scheduling work, our first, naive implementation of SWO for graph coloring produced respectable results. Even without color reuse, color grabbing, or the least constraining heuristic (the first free color found was picked), SWO matched IG on 6 problems and beat it on 10. However, on half of the remaining problems IG did better by 10 or more colors.

To explore the sensitivity of SWO such implementation details we tried the following different approaches in the constructor and prioritizer, and ran SWO using all combinations:

Construction:

With or without color grabbing

Analysis:

Either blame all nodes that receive a color outside the target set, or only the first node (in the priority sequence) that causes a new color outside the target set to be introduced. If color grabbing is used, the determination of blame is based on the final color assigned to the node.

The difference in solution quality from the worst combination to the best combination was less than 15 percent. Even when the alternative of using a standard sort instead of the ``sticky'' sort (a fairly fundamental change) was added to the mix, the spread between worst and best was still under 20 percent.