This problem has a typo in G&J. I’ll explain it once I get through the problem description.

**The problem: **Comparative Vector Inequalities. This is problem MP13 in the appendix.

**The description: **Given two sets of m-tuples, X and Y. X and Y can possibly be of different sizes (but each tuple in X and Y is always of length m). Can I find an m-tuple such that if there are K different tuples in X that satisfy , then there are less than K tuples in Y that satisfy ?

An m-tuple is an m-tuple if an only if each element of is the correspoinding element of .

The typo in G&J is that they say that it’s ok for there to be K or less (instead of strictly less) tuples in that satisfy the inequality. But my book has an “update” written on the inside back cover that says it’s wrong.

**Example: **Suppose X is:

x_{1} |
1 | 2 | 3 |

x_{2} |
4 | 5 | 6 |

x_{3} |
7 | 8 | 9 |

..and Y is:

y_{1} |
1 | 1 | 1 |

y_{2} |
4 | 4 | 4 |

y_{3} |
7 | 7 | 7 |

If we choose as (4,4,5), then both x_{2} and x_{3} are ≥ that in X, but only y_{3} is ≥ it in Y.

**Reduction: **G&J say to use Comparative Containment, which is a good choice. Comparative Containment gives you two sets R and S that are subsets of some set U (we used X in that problem, but let’s call it U to reduce confusion with the X in this problem), each with weights. In our Comparative Containment reduction, we reduced to a version where all of the weights were 1, so we’ll use that version here. The problem then asks: can we find a subset U’ of U such that there are more sets in R that have U’ as a subset than there are sets in S that have U’ as a subset?

We’ll make a set of |U| tuples, where each element in X is a 0/1 vector corresponding to an element in R. So if U was the numbers from 1-10, and an element of R was {2,4,7}, the corresponding element of X would be:

{0,1,0,1,0,0,1,0,0,0}

We do something similar for Y, where tuples correspond to elements in S.

The we pick will correspond to our U’. For *any* tuple in X or Y to be ≥ , will have to consist of only 0’s and 1’s. A tuple in X (or Y) is ≥ if it has 1’s in it in all of the places there are 1’s in , and possibly 1’s in other places too. This means that the elements in U corresponding to the 1’s in are a subset of the corresponding element of R (or S).

So the vector corresponds to a subset U’ of U that is a solution to the Comparative Containment problem.

**Difficulty: **4. The reduction itself isn’t that hard since they’re basically the same problem. But the problems themselves are a little hard to wrap your head around.