Tag Archives: X3C

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)

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.

Protected: Expected Component Sum

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

Protected: Subset Product

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

Protected: Minimum Cover

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

Protected: Minimum Edge-Cost Flow

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

Protected: Geometric Traveling Salesman

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

Protected: Acyclic Partition

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

Protected: Geometric Capacitated Spanning Tree

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

Protected: Bounded Diameter Spanning Tree

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