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.

Partially Ordered Knapsack

Continuing our “Variants on the Knapsack Problem” theme..

The problem: Partially Ordered Knapsack.  This is problem MP12 in the appendix.

The description: Like usual, we’re given a set U, where each element u in U has positive integer size s(u) and value v(u), a maximum total size B, and a target total value K.  We also are given a partial order \lessdot on the elements of U, which we can represent as a directed acyclic graph.  Can we find a subset U’ of U where the total size of all elements in U’ is at most B, the total value of all elements in U’ is at least K, and for all elements u in U’, if some other u’ is  \lessdot u’, then u’ is also in U’?

Example: Suppose we have the following 3 elements:

Item 1 2 3
Profit 3 3 5
Weight 3 3 5

If B=6 and K=6, and there is no partial order, then taking items 1 and 2 make a valid solution.  But if we add the partial order graph:

Than taking either item 1 or 2 means we have to also take item 3, which makes our size too big.  So this version can’t be solved.

Reduction: G&J have this as a “no reference” reduction, but I found a paper by Johnson and Neimi that has it, and I’m glad I did because it’s pretty slick.  The reduction is from Clique, So we’re given an undirected graph G=(V, E) and an integer K.   We need to build a partial order DAG (where the vertices will be knapsack items), and also sizes and values for each item.

The DAG has a vertex for each vertex and edge in G  (I’ll be talking about these as “vertices from V” and “vertices from E”)  Edges in the DAG connect vertices from V to the vertices from E that are incident on that vertex.  So there is no path of length more than 1 in the partial order (no edges come out of the vertices from E).

Both the value and size of each vertex from V are |E|+1, and the value and size of each vertex from E are 1.

B’ and K’ will both be set to K(|E|+1) + K(K-1)/2.  It’s worth noting that the first half of that equation will be the total profits and sizes of K vertices from V, and the second half will be total profits and sizes of the edges connecting those vertices if they form a clique.

Suppose we have a clique in G.  Then all of the vertices in the clique, plus all of the edges in the clique form a solution to the partially ordered knapsack problem, as described above.

If we have a solution to the Partially Ordered Knapsack problem, that means we have a set of vertices that respects the partial order with total value at least K’ and total size at most B’.  Since the value and size of each vertex are the same, that means that the total value = the total weight = K’ = B’.  The only way to get that is if we have K vertices from V, and K(K-1)/2 vertices from E.  Since the partial order is built such that we can’t take a vertex from E without taking a vertex from V that is an endpoint of the vertex from E, this means that we have a set of K(K-1)/2 edges in E that all have endpoints in one of K vertices from V, which forms a clique.

Difficulty: 5.  I like how the formula for B’ in the reduction is one where you can easily see what all of the pieces of it are doing, and where they all come from.

Continuous Multiple Choice Knapsack

This week we have a variant of the Knapsack problem that feels like greedy methods shold work on.  G&J actually provide several variants of this problem that the greedy approach would give us a polynomial solution.

The problem: Continuous Multiple Choice Knapsack.  This is problem MP11 in the appendix.

The description: Given a set of elements U, each element u in U has a positive size (s(u)) and value (v(u)).  We’re also given a partition of U into m disjoint sets U1 through Um, a maximum capacity C and a goal value K.   Can we pick a single element ui from each Ui, and assign each one a rational number ri between 0 and 1 to each on so that the sum of all ri*s(ui) is ≤ B and the sum of all ri*v(ui) is ≥ K?

Example: This seems like a problem where a solution similar to the greedy solution to fractional Knapsack should work- take the highest vaalue per size that you can.  This fails because you can only take 1 of each item, and you may need to take a less profitable item (in terms of ratio) with a higher total value.

For example, if partition 1 was:

Item Value Size
1 8 7
2 10 10
3 6 8

and partition 2 was:

Item Value Size
1 3 9
2 2 2
3 1 6

If K was 10, we could get 10 profit using only 9 size by taking all of item 1 from partition1 and all of item 2 from parttion 2.  But is 12, we can only do that by taking item 2 from parittion 1, which gives us a total size of 12.

Reduction: G&J say to use Partition, but the paper by Ibaraki that I have uses 0/1 Knapsack.  Define R to be a number > the max of all of the values * (the max of all of the weights -1).  We will construct a Ui set for each element in the initial Knapsack instance.  Each will each have 2 elements: ui1 has value R+v(i) and size s(i).  ui2 has value R and weight 0.  We’ll keep the same B.  Our K’ will be n*R+K.  (He doesn’t explicitly say this, instead proving that the optimial solution for this problem exists if and only if the corresponding items are taken for the 0/1 Knapsack problem.  But each element contributes at least R to the total value, whether we take ui1 or ui2.  We then either add v(i) to our value (if we take ui1) or 0 to it (if we take ui2))

Ibaraki shows that optimal solutions to this problem only ever take at most one fractional item- they take 0 or 1 of every other item.  He then shows that in this specific instance, you won’t take any fractional items.

He then proves that taking the ui1 from each set corresponds to taking ui once in the original Knapsack.  Which is pretty straightforward.

Difficulty: 6.  This is actually not that hard of a reduction, except for the need to pick a “big enough” R.  I’m not entirely sure why the chosen R is big enough, but other values aren’t.  The rating also assumes that you tell the students about the “maximum one fractional value” fact.

Integer Knapsack

MP9 is Knapsack

The next problem seems like an easy variant of Knapsack, and I tried for a while to find a quick easy reduction.  When I finally caved and looked up the reference, I found that it wasn’t easy at all.  Which made me feel good, at least, that I wasn’t missing something, but I do still feel like there should be an easier way to do this.

The problem: Integer Knapsack.  This is problem MP10 in the appendix.

The description: Given a set of elements, each item i has weight wi and profit pi, and two positive integers B and K, can we assign a non-negative integer ci to each item i such that:

  • \sum_{i=1}^{n} ci*wi ≤ B
  • \sum_{i=1}^{n} ci*pi ≥ K?

Example: This is just the classic Knapsack problem where we are allowed to take more than one of each item.   So, suppose we have 3 items:

  1. Profit 4, Weight 1
  2. Profit 6, Weight 2
  3. Profit 3, Weight 3

No matter what our B is, in the original 0/1 problem, we could only possibly get a profit of 13.  But here, if we say that B is 10, we could get a profit of 40 by taking the first item 10 times.

Reduction: It really seems very close to regular Knapsack, doesn’t it?  G&J even say that the reduction is from Sum of Subsets, just like our Knapsack reduction did.  But the reference from Lueker is actually pretty complicated:

We’re given a Sum of Subsets instance- a set S with n elements and a value K to try to hit exactly.

Define M to be 1+  the max of K, n* \sum si , and 2*n.  We’ll now create a set U for our Integer Knapsack instance with 2n elements:

Each element will be labeled uij, where i runs from 1 to n and j runs from 0 to 1.  Element uij will have profit and weight n* Mn+1+ Mi + j*si

Our K’ (and B’) will be: n*Mn+1 + \sum_{i=1}^{n} Mi  + K.

If S has a subset that sums to K, then for each element i, if we took si in the solution, we take ui1 in our Integer Knapsack solution.  Otherwise, we take ui0.

If U has an Integer Knapsack solution, we know that we have non-negative integer values cij such that \sum_{i=1}^{n} \sum_{j=0}^{1} cij*uij = K’.  Because of the way we chose M, if we divide K’ by Mn+1 and round down, we get n.  Because each uij has Mn+1 in it, dividing the summation side by Mn+1 gets us a number at least as big as the sum of the cij values.  So we can say that \sum_{i=1}^{n}\sum_{j=0}^{1} yij is ≤ n.  Thus, each element is taken at most n times.

Now we can go back to the original equation: \sum_{i=1}^{n} \sum_{j=0}^{1} cij*uij = K’ and do algebra.  We learn that in fact, each cij is 0 or 1, and that ci0 + ci1 = 1 for all i (so we never take both ci0 and ci1), and that the values of ci1 are 0/1 solutions to the corresponding elements in the Sum of Subsets problem.

Difficulty: 7.  There seems to be no natural reason to for this definition of  M except “that’s what made it work”.  I wish there was an easier reduction.

Traveling Salesman Polytope Non-Adjacency

This may be the hardest problem description to understand that I’ve done.  I’m still not sure I really understand the problem, let alone the reduction.  So I apologize in advance for what you’re about to read.

The problem: Traveling Salesman Polytope Non-Adjacency.  This is problem MP8 in the appendix.

The description:  I’ve got a lot of this definition from the paper by Papadimitriou that has the reduction.  We’ll take it slowly:

Suppose we have a complete, undirected, weighted graph G=(V, E).  Let |V| = n.  This means that |E| = n*(n-1)/2.  We can number these edges, and then denote whether a potential tour is “using” an edge or not by a 0/1 vector.  So a vector (0,1,1,0,1,0) means that the solution we’re considering uses edges 2,3, and 5.  (This may or may not be a legal tour).  Each legal Hamiltonian Cycle can be represented as one of these vectors.  This gives us a set of 0/1 vectors.  We can think of these vectors as points in Rn.  We then want to talk about the convex hull of these points.

Two vertices on this convex hull are defined to be “adjacent” if they are connected by an edge on the convex hull.

So, the problem asks: Given two Hamiltonian Cycles on G, are they non-adjacent on this convex hull?

(Yes, it’s weird that the problem never uses the distances between the vertices.  I think this is really “Hamiltonian Cycle Polytope Non-Adjacency”.  In fact, I think this makes more sense because the graph that is built in the reduction is not a complete graph)

Example: This is pretty hard to visualize, so let’s start with a simple graph:

Let’s list edges in alphabetical order in our vector. The vector will have 6 elements in alphabetical order: ab, ac, ad, bc, bd, cd

So the tours we have are:

  • ABCDA, represented as (1,0,1,1,0,1)
  • ABDCA, represented as (1,1,0,0,1,1)
  • ACBDA, represented as (0,1,1,1,1,0)

..and that’s really it.  All of the other tours are either reversals of the above (such as ADCBA), or an above tour shifted by starting at a different point (like BCDAB), which use the same edges and thus create the same vectors.

So, we are left with 3 points in 6-dimensional space.  Obviously, any 2 points in that space are adjacent.  If we start with a graph with 5 vertices:

we have 10 dimensions to our vector, for the edges ab, ac, ad, ae, bc, bd, be, cd, ce, and de. We also have 12 tour vectors. I won’t list them all, but for example, the tour ABCDEA would be represented by (1,0,0,1,1,0,0,1,0,1).  In this case, the need to define what the convex hull of those points are, and whether 2 tours are adjacent becomes harder to see.

Reduction:

Papadimitriou uses 3SAT.  So we’re given a set of m clauses over p variables, and we need to build a graph and two tours.  The graph he builds is made up of a series of widgets.  These widgets are designed to force certain edges to be used if the graph is to have a Hamiltonian Cycle.  The idea is that he constructs the widgets in a way that we can construct 2 cycles that are non-adjacent if and only if the formula was satisfiable.  So for example, here is his “exclusive or” subgraph (p. 316 of the paper):

In this subgraph, a Hamiltonian Cycle needs to go from u to u’ or v to v’ (it can’t do both, it can’t do neither).  By constructing ever-more complicated versions of this, he builds a graph.  Here’s how it looks for the formula B = (x1, x2, x3) ∧ (x1, x2, ~x3) ∧ (~x1, ~x2, ~x3) (p. 319 of the paper):

The bold lines in the figure above correspond to setting all variables to true.  There is also a circuit corresponding to making all variables false.  (We assume this satisfies at least one clause because if it didn’t, we have a Satisfiability instance where each clause has at least one positive literal, which is trivially satisfiable).  It turns out that every edge in this graph belongs to at least one of these two cycles.  For these two cycles to not be adjacent in the polytope, there needs to be some other circuit “between” them.  This circuit corresponds to a legal way to set all of the variables to make all clauses true.  If no such circuit exists (and the formula is not satisfiable), then the 2 tours are adjacent.

Difficulty: 9.  I can see what he’s doing, but I really have trouble following how he gets there.  Part of the difficulty with this problem is that it’s such a weird non-intuitive (to me) definition of “adjacency”.  I wonder if there is a better one out there.  Another source of difficulty is what I think of as confusion between TSP and HC.  The crazy widgets don’t help either.

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.

Open Hemisphere

I’m going to be out of town for the next 2 weeks, so we’ll be going on a bit of a hiatus.

The problem: Open Hemisphere.  This is problem MP6 in the appendix.

The description: Given a set X of m-tuples of integers, and a positive number K, can we find an m-tuple  \bar{y} of rationals such that at least K of the m-tuples, when multiplied by \bar{y}, are at least 0?

Example: Suppose our tuples were:

  1. {1,1,1}
  2. {-1,-1,-1}
  3. {1,-1,1}
  4. {-1,1,-1}

If K = 2, we can choose \bar{y} to be {1,0,1}.  This multiplied by tuples 1 and 3 would be positive (with a value of 2).  We could have also chosen {-1,0,-1} to make the multiplication with tuples 2 and 4 positive.  I don’t think there is a legal \bar{y} if K=3.  There certainly isn’t if K=4 (you can’t make both tuple 1 and tuple 2 positive simultaneously).

Reduction: Johnson and Preparata use Max-2-Sat.   So we’re given a 2-Sat instance with s clauses, m variables, and a target N, the number of clauses we need to satisfy.  Let t = \lceil log_{2}(ms+1) \rceil and d = m+1+3t.  We will create d-tuples as follows.

  • “A” vectors: 23t copies of “positive” and “negative” vectors for each variable.  So variable i has vectors Ai = i-1 0’s, followed by 1 followed by m-i 0’s, followed by 1, followed by each permutation of 1 or -1 of length 3t.  ~Ai is similar, except the first 1 is replaced by a -1.
  • 2t “B” vectors for each variable (positive and negative).  So variable i has vectors Bi = i-1 0’s, followed by 4, followed by m-i 0’s followed y -2, followed by 2t 0’s, followed by each permutation of 1 or -1 of length t.  ~Bi is similar, but the 4 is replaced by -4.
  • One “C” vector for each clause.  If the clause had variables xi and xj, the clause would be: i-1 0’s followed by 4*the sign of xi, followed by j-1 0’s, followed by 4* the sign of xj followed by m-j 0’s followed by 1 followed by 3t 0’s.

By “the sign of xi“, I mean 1 if xi shows up as a positive literal, and -1 if it shows up as a negated literal.  It’s also worth noting that since t is based on the log of the input size, creating a number of vectors that is exponential in t still keeps the input size of our hemisphere instance polynomial.

Our K will be 2m+23t+m*2t+N.  (All of the A tuples, half of the B tuples, and N of the C tuples)

If we have a Max-2-Sat solution, here’s how you build the \bar{y}:

  • Positions 1-m correspond to variables.  If the variable is set positively, put a 1 in that position.  If the variable is set negatively, put a -1 in that position.
  • Put a 1.5 in position m+1
  • Put a 0 everywhere else.

This will multiply positively with all A tuples, half of the B tuples, and  N of the C tuples.

If we have a hemisphere solution, it has to fit certain criteria:

  • At least 2m*23t-22t of the A vectors multiply positivly with our solution (this is how many you need even if all B and C vectors multiply positively)
  • Position m+1 of the solution vector is > 0 (otherwise not enough A vectors are positive)
  • At most 2t Bi vectors multiply positively with our solution for each variable i.  (Position m+1 of the B vector is the -2.  If we have more than 2t Bi vectors we’ll set position m+1 in the solution vector negative)
  • Position m+1 of the solution vector is  at least as big as the sum of the absolute values of the values in positions m+2+2t through m+1 + 3 (If it wasn’t, the limit on the B vectors would mean we wouldn’t be able to take enough A vectors to get a hemisphere solution)
  • Each value in the first m positions in the solution vector is at least as big as the absolute value of (position m+1) /4  (You can prove this by contradiction using algebra).  Importantly, this means those values can’t can’t be 0.
  • We must have at least N C tuples that multiply positively with the solution vector (given the limits on A and B).

Using these facts, we can find the ways to set the variables: Each of the first m positions in the solution vector correspond to a variable.  If the value at that position is positive, set it to true, if the value is negative, set it to false.  This will satisfy the N clauses that correspond to the C tuples that were made positive in the hemisphere solution.

Difficulty: 9.  Notice how much work has to happen to get around the fact that the hemisphere could have rational answers.  Also, notice how many tuples you need to get this reduction.  I’m also not 100% convinced yet that there isn’t a hole in the various claims about how the hemisphere solution has to behave that allows some weird combination of values to fall through.

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)

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.

 

Cost-Parametric Linear Programming

This is a hard reduction that I’m not sure I understand.  I’m sure if I was better at vector operations, I’d be more able to figure it out.

The problem: Cost-Parametric Linear Programming.  This is problem MP3 in the appendix.

The description: Given a set of integer constraints (\bar{x},b) as in Integer Programming, (except that the inequalities are \geq instead of \leq for some reason, but we can always multiply by -1 to flip the constraints) and a set J that is a subset of  indices of the variables in \bar{x}.  Can we find an m-tuple \bar{c} with rational values such that \sqrt{\bar{c} \cdot \bar{c} }\leq q and for all feasible non-negative m-tuples \bar{y} that satisfy the constraints,  the minimum of \sum_{j \in J}( c_j * y_j) > \frac{1}{2}* max \{|c_j| : j \in J\} +\sum_{j \in J} min \{0,c_j\}

Example: Ok, here’s a pretty simple situation.  Suppose we have 3 variables, with constraints:

x_1 + x_2 + x+3 \leq 1  (Or, technically, -x_1 - x_2 - x_3 \geq -1)

x_1 \geq .3

x_2 \geq .4

x_3 \geq .2

Now, suppose we choose a \bar{c} of (1,1,0} and a J of {1,2}.  So in this case, the minimum of \sum_{j \in J}( c_i * y_i) would be .3 + .4 = .7.  That needs to be more than \frac{1}{2}* max \{|c_j| : j \in J\} +\sum_{j \in J} min \{0,c_j\}  This comes out to .5 + 0, so it works.  So, with this \bar{c}, we need \sqrt{\bar{c} \cdot \bar{c} }\leq q , so a q > \sqrt{2} makes this solution correct.  There may be different values for \bar{c} that will also work on smaller q’s.

Reduction: G&J say that the reduction is from 3SAT, but I think the paper by Jersolow uses DNF Non-Tautology. Given a logical formula in DNF form, he builds a linear inequality system. All variables in formula become variables in the linear program.  For each clause, every variable has a constraint that it’s \leq 1.  (and, I think implicitly, \geq 0).  If the variable shows up in a literal positively, we add the constraint that it is \geq 1.  If it shows up negatively, we have a constraint that it’s \leq 0.  This means that we have a solution to the constraints if and only if we set the variables to the truth values that make the clause true.  (Remember, we have a DNF formula, so each clause is a conjunction- we need to make each variable true).

He then shows that the minimum way to solve the constraints (since it’s in DNF, that means making one clause true) is \leq \frac{1}{2}* max \{|c_j| : j \in 1..m \} +\sum_{j=1}^ m min \{0,c_j\} is true for all \bar{c} if and only if A is a tautology.  From there he goes on to show that our problem instance holds.

I’m pretty confused by the logic- especially seems it looks like he’s saying that his problem is true if and only if the original problem is a tautology, when non-tautology is what we’re supposed to be reducing from.

Difficulty 9.  This is a hard problem to understand,  and the reduction is hard to follow as well.   It’s very possible I’m not understanding something in the paper.