K-Relevancy

Back from my trip, we pick up with a problem where I couldn’t find a simple reduction, and man I wish I could.

The problem: K-Relevancy.  This is problem MP7 in the appendix.

The description: Given a set X of (\bar{x}, b) pairs, where \bar{x} is an m-tuple of integers, and a positive integer K, can I find a subset X’ of X, of K or less elements, such that any m-tuple \bar{y} that solves \bar{x} \cdot \bar{y} \leq b for all \bar{x} in X’, also solves it for all pairs in X?

Example: Here’s a pretty easy example that I think gets the point across:

X1: 2y1 + 2y2  \leq 5

X2: 4y1 + 4y2 \leq 10

Obviously, any values of y1 and y2 that make the first inequality true also make the second one true.

Here’s a slightly more interesting one:

X1: y1+y2 \leq 10

X2: y1-y2 \leq 10

X3 y1 \leq 10

X1 defines a half-plane where points like y1=100, y2=-100 exist.  But X2 defines an intersecting halfplane, where the only legal solutions have y1 \leq 10.  So the third equation isn’t necessary.

Reduction: G&J say that this reduces from X3C, but I can’t see how.  They refer me to a technical report by Reiss and Dobkin, which I found published by Dobkin and Reiss in Theoretical Computer Science.  But the thrust of this paper is to talk about how Linear Programming is kind of in its own complexity class, and to create a notion of “LP-Completeness”.  They show that if K = |X|-1, relevancy is the same as Linear Programming.  They also say that you can extend the idea that Johnson and Preparata use in the Hemisphere problem to other problems like Relevancy.  (Hemisphere is LP-Complete if we want to know if all or no points are in the Hemisphere).

The problem I have with that is that Johnson and Preparate’s reduction used Max-2-Sat, not X3C, and the reduction there seems pretty tailored towards the Hemisphere problem, and I don’t see an easy way to get from there to our problem. So I don’t really know what they mean.

But, Dobkin and Reiss do show how Hemisphere and Relevancy relate in the LP-Complete world, so we can follow that chain of reductions:

  • So, Hemisphere is equivalent to “Origin Interior” (given a set of points on the unit sphere, is the origin outside the convex hull of those points?), which they claim is the same problem restated.
  • Origin Interior is equivalent to “Extreme point” (given a set of points on the unit sphere and any point, is that point outside the convex hull of our pointset?), which pretty clearly is the same problem.
  • Extreme point is equivalent to “Hyperplane Halfplane Intersection” (given a set of half-spaces, and a hyperplane, does our hyperplane intersect the intersection of all of the halfspaces?).  They say this is true based on the “geometric duality concept”.
  • Hyperplane Halfplane Intersection is just a geometric interpretation of Relevancy, so those problems are equivalent.

I think that the arguments that show that these problems are all equivalent to LP will also work as reductions in our NP-Complete world.  But man, I really want to know why G&J said this reduction was from X3C, and whether an easy reduction from there exists.

Difficulty: 8, but I hope something easier exists.

Leave a Reply

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