next up previous
Next: About this document Up: No Title Previous: Frequency Block Scheduling

Our attack

If all of the customer requests were of the same amount of frequency, this problem reduces to coloring an interval graph. Such colorings can be found in tex2html_wrap_inline19 time by sorting the intervals and assigning colors from left to right. The chromatic number is defined by the maximum number of intervals which can be stabbed by one point.

This interval graph coloring algorithm provides for an immediate r-factor approximation, where r is the ratio of the largest to smallest frequency request. Simply ignore the weights, and treat it as an interval graph. Muthu and I (prior to reading group) had used this idea to get an tex2html_wrap_inline25 factor approximation by partitioning the weights into bins by approximate size, and solving each bin independently.

Muthu and Mike Paterson claim to have proven this problem hard in the general case by using a reduction to partition. We tried to reproduce this in reading group, but found it very difficult. The issue is that one must build a gadget that forces a group of rectangular blocks to ``pack'' in a certain way - however there is great flexibility in the way you can move the blocks around. Joe claimed a possible proof at the end of the session, but it was not clear that he hadn't just constructed too complicated an example for the rest of us to understand...

More embarrassingly, we could not come up with an easy example of a set of blocks which could not be packed so at to realize the maximum sum of weights which can be stabbed by one point. This made us somewhat uncomfortable with out state of knowledge about the problem.

Steve believes that a heuristic similar to standard bin-packing heuristics (like first-fit decreasing) will give a constant factor approximation ratio. Only the proof is lacking to complete the result.


next up previous
Next: About this document Up: No Title Previous: Frequency Block Scheduling

Steve Skiena
Thu Oct 16 16:58:41 EDT 1997