Suppose I have a set of n ordered tuples, all of the same, fixed dimension. The tuples' values are integers, with #
s indicating an integer I don't care about. For example:
{ (1,2,5), (4,2,3), (1,2,#), (#,2,3) }
Tuples can be combined so long as they don't disagree about anything. For example, (1,2,#)
and (#,2,3)
can be combined into (1,2,3)
. Therefore, we can simplify the above set by combining the last two elements:
{ (1,2,5), (4,2,3), (1,2,3) }
The goal is to simplify the set as much as possible. We can't simplify from here any more, but by simplifying in a different way, we could have done better by combining the 1st with the 3rd and the 2nd with the 4th (hence, this problem is not convex):
{ (1,2,5), (4,2,3) }
My question:
- Is this a well-known problem by a different name? (E.g., give a reduction from some NP-complete problem, perhaps?) It's related to the set-cover problem, but somewhat different since elements can be combined and not everything need be chosen.
- What algorithms can I use to solve this, even approximately? Speed is important; I solved a similar, simpler problem in expected O(n); equivalent performance would be ideal.
Call tuples containing at least one #
"free tuples" (vs. "complete tuples"). Observation: WLOG every tuple is free: combining a free tuple with a complete tuple or a complete tuple with a complete tuple is never suboptimal, so we can preprocess all such combinations first, then remove all complete tuples--since by construction, nothing can combine with them.