Tag Archives: Difficulty 8

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.

Feasible Basis Extension

The paper for this one is one of the older ones I have- it was published in 1972, but they say it was first submitted in 1970, which would be before Cook’s paper came out.

The problem: Feasible Basis Extension.  This is problem MP4 in the appendix.

The description: Given an mxn matrix A of integers (m < n), and a column vector  \bar{a} of size m, and a subset S of <m columns of A, can  we find a non-singular (i.e., invertible) mxm  submatrix B of A, such that:

  • B contains all of the columns of S, and
  • All of the elements of the vector \bar{x}, where \bar{x} = B-1 * \bar{a} are  \geq 0?

Example: I’ll try to keep the matrix calculations simple.  Suppose A was:

1 2 3
4 5 6

\bar{a} was:

\frac{1}{6}
\frac{1}{2}

and S was just the second column.  Then B has to be a 2×2 submatrix of A that includes the second column, for example:

1 2
4 5

The inverse of this is:

\frac{-5}{3} \frac{2}{3}
\frac{4}{3} \frac{-1}{3}

Which, if we multiply by \bar{a}, gives us:

\frac{1}{18}
\frac{1}{18}

Reduction:

The paper by Murty is from 1972, so doesn’t really follow the same reduction structure we’re used to.  The basic idea is to start with an instance of TSP, and realize that we can write a tour as an nxn matrix X where xij = 1 if the tour goes from city i to city j, and 0 otherwise.  (This is basically a way of taking a permutation of the n cities, and stretching it out to an nxn 0-1 matrix).  We can then write the TSP problem as a set of constraints: Each row in the solution sums to exactly 1, each column in the solution sums to exactly 1, and all entries are \geq 0.  We are trying to minimize the cost of all of the 1 entries in the solution.   We can get the decision problem by adding a new constraint: That the costs of all of the entries is \leq the K from the TSP instance.

He then shows that if this system has a feasible basis, it must be a tour that satisfies the TSP instance.  The proof involves lemmas that talk about the “convex polytope” of the constraints, which I think needs some pretty sophisticated linear programming familiarity to follow.

Difficulty: 8.  Maybe less if you are teaching a mathematical programming class- I don’t think the ideas are hard, but I do think they’re not likely to come up in an algorithms class.

 

Protected: Deadlock Avoidance

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

Protected: No-Wait Flow-Shop Scheduling

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

Protected: Scheduling with Individual Deadlines

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

Protected: Safety of File Protection Systems

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

Protected: Boyce-Codd Normal Form Violation

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

Protected: Minimum Cardinality Key

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

Protected: External Macro Data Compression

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

Protected: String-To-String Correction

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