Comparative Vector Inequalites

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 \bar{z} such that if there are K different tuples \bar{x_i} in X that satisfy \bar{x_i} \geq \bar{z}, then there are less than K tuples \bar{y_i} in Y that satisfy \bar{y_i} \geq \bar{z}?

An m-tuple \bar{u} is \geq an m-tuple \bar{v} if an only if each element of \bar{u} is \geq the correspoinding element of \bar{v}.

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 \bar{y} 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:

x1 1 2 3
x2 4 5 6
x3 7 8 9

..and Y is:

y1 1 1 1
y2 4 4 4
y3 7 7 7

If we choose \bar{z} as (4,4,5), then both x2 and x3 are ≥ that in X, but only y3 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 \bar{z} we pick will correspond to our U’. For any tuple in X or Y to be ≥ \bar{z}, \bar{z} will have to consist of only 0’s and 1’s.  A tuple in X (or Y) is ≥ \bar{z} if it has 1’s in it in all of the places there are 1’s in \bar{z}, and possibly 1’s in other places too.  This means that the elements in U corresponding to the 1’s in \bar{z} are a subset of the corresponding element of R (or S).

So the \bar{z} 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.

Leave a Reply

Your email address will not be published. Required fields are marked *