Cost-Parametric Linear Programming

This is a hard reduction that I’m not sure I understand.  I’m sure if I was better at vector operations, I’d be more able to figure it out.

The problem: Cost-Parametric Linear Programming.  This is problem MP3 in the appendix.

The description: Given a set of integer constraints (\bar{x},b) as in Integer Programming, (except that the inequalities are \geq instead of \leq for some reason, but we can always multiply by -1 to flip the constraints) and a set J that is a subset of  indices of the variables in \bar{x}.  Can we find an m-tuple \bar{c} with rational values such that \sqrt{\bar{c} \cdot \bar{c} }\leq q and for all feasible non-negative m-tuples \bar{y} that satisfy the constraints,  the minimum of \sum_{j \in J}( c_j * y_j) > \frac{1}{2}* max \{|c_j| : j \in J\} +\sum_{j \in J} min \{0,c_j\}

Example: Ok, here’s a pretty simple situation.  Suppose we have 3 variables, with constraints:

x_1 + x_2 + x+3 \leq 1  (Or, technically, -x_1 - x_2 - x_3 \geq -1)

x_1 \geq .3

x_2 \geq .4

x_3 \geq .2

Now, suppose we choose a \bar{c} of (1,1,0} and a J of {1,2}.  So in this case, the minimum of \sum_{j \in J}( c_i * y_i) would be .3 + .4 = .7.  That needs to be more than \frac{1}{2}* max \{|c_j| : j \in J\} +\sum_{j \in J} min \{0,c_j\}  This comes out to .5 + 0, so it works.  So, with this \bar{c}, we need \sqrt{\bar{c} \cdot \bar{c} }\leq q , so a q > \sqrt{2} makes this solution correct.  There may be different values for \bar{c} that will also work on smaller q’s.

Reduction: G&J say that the reduction is from 3SAT, but I think the paper by Jersolow uses DNF Non-Tautology. Given a logical formula in DNF form, he builds a linear inequality system. All variables in formula become variables in the linear program.  For each clause, every variable has a constraint that it’s \leq 1.  (and, I think implicitly, \geq 0).  If the variable shows up in a literal positively, we add the constraint that it is \geq 1.  If it shows up negatively, we have a constraint that it’s \leq 0.  This means that we have a solution to the constraints if and only if we set the variables to the truth values that make the clause true.  (Remember, we have a DNF formula, so each clause is a conjunction- we need to make each variable true).

He then shows that the minimum way to solve the constraints (since it’s in DNF, that means making one clause true) is \leq \frac{1}{2}* max \{|c_j| : j \in 1..m \} +\sum_{j=1}^ m min \{0,c_j\} is true for all \bar{c} if and only if A is a tautology.  From there he goes on to show that our problem instance holds.

I’m pretty confused by the logic- especially seems it looks like he’s saying that his problem is true if and only if the original problem is a tautology, when non-tautology is what we’re supposed to be reducing from.

Difficulty 9.  This is a hard problem to understand,  and the reduction is hard to follow as well.   It’s very possible I’m not understanding something in the paper.

Leave a Reply

Your email address will not be published. Required fields are marked *