Tag Archives: No G&J reference

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)

Protected: Staff Scheduling

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

Protected: Rectilinear Picture Compression

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: Capacity Assignment

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

Protected: Multiple Copy File Allocation

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

Protected: Dynamic Storage Allocation

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

Protected: Ratio Clique

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

Protected: Bin Packing Take 2

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