Category Archives: Appendix- Mathematical Programming

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:


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.


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.


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.

Protected: Minimum Weight Solution to Linear Equations

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

Protected: Feasible Basis Extension

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

Protected: Cost-Parametric Linear Programming

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