Tag Archives: X3C

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.

Minimum Weight Solution to Linear Equations

After the last few problems in this chapter were so hard, I was worried when I saw this was a “no reference provided” problem.  Luckily, I think I was able to figure the reduction out.

The problem: Minimum Weight Solution to Linear Equations.  This is problem MP5 in the appendix.

The description: Given a set of equations X, where each equation consists of an m-tuple of integers \bar{x} and an integer b.  We’re also given a positive integer K \leq m.  Can we find an m-tuple \bar{y} with rational entries such that at most K of y’s entries are non-zero and \bar{x} \cdot \bar{y} = b for all equations in X?

Example: I find it easier to write the equations out.  Suppose we have:

3y1+2y2+y3 = 7

4y1+3y2 + 7y3 = 10

If we set K=2, that means that only 2 of the 3 y values in the solution can be non-zero (so we need at least one 0).  Choosing y1=1, y2=2, y3=0 works.

Reduction: G&J don’t give the reduction, but in the comments, they say it’s polynomial if K=m.  That plus the use of “X” (the set in X3C) made me think that the reduction from X3C had the \bar{y} be related to the sets chosen from C.

So our X3C instance has a set X of 3q elements, and a set C of collections of 3-element subsets of X.  We’ll set m (the size of the tuples in our equations) to |C|.  Our equation set X’ will have 3q equations.  Each equation will correspond to an element in X, and the positions of its \bar{x} vector will correspond to the sets in C.  Each vector element will have a 1 in the positions where the element exists in the set in C, and 0 otherwise.  Our b value will be 1 for each equation, and K will be q (we want q of the variables to be 1)

So, for example, if X = {1,2,3,4,5,6}, and C was {1,2,3}, {4,5,6}, {2,4,5}, we would have 6 equations:

y1 = 1   (the equation for element 1)

y1 + y3 = 1 (the equation for element 2, which appears in sets 1 and 3)

y1 = 1 (the equation for element 3)

y2+y3 = 1 (the equation for element 4)

y2+y3 = 1 (the equation for element 5)

y2 = 1 (the equation for element 6)

Since this is a small and simple X3C instance, there is a lot of redundancy in the equations.  But hopefully it’s clear how it relates to the initial instance: We’re asking if we can create a 0/1 tuple that solves each of these equations (fractional values for the y variables won’t work because if we do that we will have more than K non-zero variable values).  Setting a variable to 1 means “choosing” that set in the X3C instance.  Having the equation be true means that we have found exactly one set in C’ holding that element of X.  Having all of the equations be true means we have found a C’ that holds exactly one copy of all elements in X (thus solving the X3C instance).

Difficulty: 5, assuming I didn’t mess anything up.  It’s very tempting to set up the equations in the wrong way (for example, making there be |C| equations of 3q-tuples)

Protected: Staff Scheduling

This content is password protected. To view it please enter your password below:

Protected: Expected Component Sum

This content is password protected. To view it please enter your password below:

Protected: Subset Product

This content is password protected. To view it please enter your password below:

Protected: Minimum Cover

This content is password protected. To view it please enter your password below:

Protected: Minimum Edge-Cost Flow

This content is password protected. To view it please enter your password below:

Protected: Geometric Traveling Salesman

This content is password protected. To view it please enter your password below:

Protected: Acyclic Partition

This content is password protected. To view it please enter your password below:

Protected: Geometric Capacitated Spanning Tree

This content is password protected. To view it please enter your password below: