Tag Archives: uncited reduction

Integer Programming

On to a new section of the appendix!

The problem: Integer Programming.  This is problem MP1 in the appendix.

The description: Given a set of X of pairs (\bar{x},b), where \bar{x} is an m-tuple of integers, and b is an integer.  We’re also given an m-tuple \bar{c} and an integer B.

Can we find an m-tuple of integers \bar{y} such that:

  • \bar{x}*\bar{y} \leq b for each (\bar{x},b) pair
  • \bar{c}*\bar{y} \geq B.

Example: The definition above kind of hides the way we commonly think of integer (or linear) programming.  The X set is the set of constraints, and the \bar{x} and B make the objective function.  So, the set ((1,2,3,4),100) really corresponds to the constraint  1x 1+2x2+3x3+4x4 \leq 100.

Here is a simple Integer Programming problem written in the way we’re probably more used to seeing:

Given constraints:

x1 + x2 \leq 5

10x1 + 6x2 \leq 45

Maximize 5x1 + 4x2 (Or, as a decision problem, can 5x1 + 4x2 be \geq 23?

The answer is yes: If x1=3 and x2 = 2, we satisfy both constraints and get an objective value of 23.

Notice that if we allowed non-integer values for our variables, we would have a linear program, and could get to an objective value of 23.75 by setting x1=3.75 and x2=1.25.

Reduction: Karp’s paper uses 3SAT, which is fine, but it’s hard to see how the objective function works there.  I think a much more natural reduction is from Knapsack.

So we’re given a set of n items, each item i has a profit pi and weight wi.  We’re given a knapsack capacity B and a goal profit K.

Our constraints will be:

x1*w1+… xn*wn \leq B  (keep the total weight at B or less)

xi \leq 1 for all i (I can take at most 1 of each item)

-1*xi \leq 0 for all i (Each xi has to be at least 0)

The last sets of constraints force each xi variable to be either 0 or 1.

The objective function asks:

p1*x1 + … + pn*xn \leq B?

I think it’s pretty clear that this is exactly the rules for Knapsack written as an Integer Programming problem.

Difficulty: 3.  I think this might be too easy for a homework problem because the proof part of the reduction (Knapsack says “yes” if and only if  IP says “yes”) is trivial.  But the need for the last set of constraints (that each variable is >=0, written as a <= equation) is a fun wrinkle that will mess up some people.

Staff Scheduling

This one has no reference in G&J, but I think it’s easy enough for me (or a student) to figure out.

The problem: Staff Scheduling.  This is problem SS20 in the appendix.

The description: Given a collection C of m-tuples, each tuple consisting only of 0’s and 1’s, and each tuple having the same amount (k) of 1’s.  These represent possible schedules we can give a worker.  We’re also given a “requirement” m-tuple consisting of m non-negative integers, and a number N of workers.  Can we map each c in C to a non-negative integer (representing the number of workers we assign to that schedule) such that the total number of all integers is N or less, and the requirement tuple is met?

Example: I think this is easier to explain with an example.  Suppose we had 4-tuples (corresponding to 4 “work periods”) and C is the tuples:

0 0 1 1
1 1 0 0
1 0 0 1
0 1 1 0
0 1 0 1

Our requirement tuple is:

2 1 4 3

Then one possible schedule would be:

  • 3 people with the first schedule (0,0,1,1)
  • 2 people with the third schedule (1,0,0,1)
  • 1 person with the fourth schedule (0,1,1,0)

..for a total of 6 workers. I think that’s the best you can do, since the first and third time periods have no schedules in common, and there is a total requirement of 6 workers for those time periods.

Reduction: G&J don’t give a reference, but they do suggest to use X3C.   So we’re given a set X of 3q elements, and a collection C of 3-element subsets of X.  The set C’ that we’ll build will be a set of “3q-tuples”, one position corresponding to each element in X.  There will be one tuple for each triple in C.  The tuples will have 1’s in the 3 positions corresponding to the elements in the triple in C, and 0’s everywhere else.  The R-tuple will be all 1’s, and N will be equal to q.

The Staff Scheduling instance we’ve built needs to choose q different tuples to be successful, and that set of tuples will correspond to a solution to the original X3C instance.

Difficulty: 4, assuming I didn’t miss anything.  If you’ve previously explained X3C to your students, this would be a good homework problem.

Three-Way Matching of Integers

This is an interesting variant on the Three-Dimensional Matching problem that will be used in the next reduction.  Since I think it would make a good easy homework problem, I’m posting it mainly as a reminder to myself to use it.

The problem: Three-Way Matching of Integers.  This problem isn’t in the appendix, but the paper by Papadimitriou and Kanellakis that describes it refers to G&J for the reduction.  I think that it’s because it’s seen as a “trivial” extension of Numerical Three-Dimensional Matching.

The description: Given a set A with n integers {a1 .. an), and a set B with 2n integers (b1, b2n), can we split B into n pairs of elements, where each pair Pi={bj, bk}  and the sum of ai+bj+ bk = the same constant c for all i?  (Notice that c will be 1/n of the sum of all of the elements in A and B)

Example: I think the problem is simpler than the description.  Suppose A = {1,2,3}, and B = {}.  Then c will be 15, and P1 = {6,8}, P2 = {4,9}, P3 = {5,7}.

Reduction:  This is very close to Numerical Three-Dimensional Matching, so we’ll start there.  So we’re given 3 sets X, Y, and Z, with n elements, and a bound B.  We can assume that B = 1/n of the sum of all of the elements in X, Y, and Z.

We can’t just set A=X, and B= Y∪Z, because we need to make sure that a solution to our problem doesn’t build a Pi that takes 2 elements from Y (or Z).  The fix is to add B to all of the elements of Y before putting them in B.  So now c will be 2B (the old B that a triple adds to, plus the B we added to the element from Y that we need).  This guarantees that each Pi will take one element that came from Y, and one element that came from Z.

Difficulty: 3.  I don’t think this is trivial since we have to change the original problem a bit in our reduction, but I think it is a change that’s not hard for people to figure out.  Though you might convince me this should be a 2 instead.

Protected: Scheduling with Individual Deadlines

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

Protected: Conjunctive Boolean Query

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

Protected: Regular Expression Substitution

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

Protected: Sparse Matrix Compression

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

Protected: Hitting String

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

Protected: Capacity Assignment

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