It occurs to me that it might be easier to reduce either Set Cover or Set Packing to my blocking problem. The two problems are duals of each other, meaning that you can verify if you've hit a minimum in one, by comparing it to the maximum of the other. Since one rarely finds an optimal solution to these sorts of things, the next best thing is to look how far apart the dual solutions are and note that the optimal result has to be somewhere between them. So, if they are close, you can probably say "good enough" and get on with life.
I think Set Cover might reduce more naturally, but even it is going to take some manipulating. Informally, the Set Cover problem is trying to find the smallest collection from a family of subsets where the union gives you the whole set. Set Packing does the opposite, it tries to find the biggest group of disjoint subsets. The fact that these are dual problems is left as an exercise to the reader.
Anyway, the idea is that one can view the blocks as subsets covering queries. The idea is to find a group of blocks that satisfies all the queries. It's a little stickier than that, because there's the redundancy that comes from multiple queries (partitioning the data to optimize a single query is trivial; just put all the relevant rows for that query in one block and put everything else in another).
Another one that might work is Subset Sum (find a subset of numbers that adds up to a given value). While not in the "original 21" problems, it seems like it might work. (There are hundreds of NP-Complete problems and you can legitimately reduce from any of them, but that the canon of 21 are universally accepted, so it adds some street cred). I worked on this a bit this evening, but hit a few snags that seemed rather formidable. Still, I'm not ruling it out.
No comments:
Post a Comment