Monthly Archives: August 2018

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.