Tag Archives: Difficulty 9

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.

Timetable Design

We’ve now entered the “Miscellaneous” section of the Sequencing and Scheduling chapter.

The problem: Timetable Design.  This is problem SS19 in the appendix.

The description: (I’m using the description in the paper by Even, Itai, and Shamir, because I think it’s clearer than G&J’s definition): We’re given a set H (of hours to schedule), a collection of N “teachers”, each teacher is available for some subset of the H hours.  We’re also given a collection of M “Classes”, each class is available to be taught for some subset of the H hours. We’re also given an NxM matrix R of requirements:  Rij is the number of hours teacher i needs to teach class j for.   Can create a function f: TxCxH->{0,1} such that f(t,c,h) is 1 if teacher T is teaching class c at time h (and 0 otherwise)?  The function needs to respect the following rules:

  • If f(i,j,h) is 1, then h is in Ti and Cj  (we only schedule teachers and classes when they’re available)
  • The sum of f(i,j,h) over all h = Rij  (Each teacher teaches each class the number of hours they’re supposed to
  • The sum of f(i,j,h) over all i <= 1  (Each class has at most 1 teacher in each time period)
  • The sum of (i,j,h) over all i <= 1 (Each teacher can only teach 1 class per time slot).

Example:  Suppose H was {1,2,3,4,5}

We have 3 teachers:

  • T1 is available at {1,2,3}
  • T2 is available at {3,4,5}
  • T3 is available at {1,3,5}

..and 3 classes:

  • C1 is available at {2,4}
  • C2 is available at {1,5}
  • C3 is available at {2,3}

If R was:

1 1 0
1 0 1
0 1 1

(Teachers are rows, so T1 needs 1 hour of C1, 1 hour of C2, and none of C3, this won’t be satisfiable, since neither T2 nor T3 can teach C3 during hour 2, and someone has to.  If we change C3 to be available at {2,3,5}, then this becomes satisfiable:

  • T1 can only teach C1 at time 2, and C2 at time 1
  • T2 can only teach C1 at time 4, and C3 can be either time 3 or 5.  Let’s pick 5.
  • T3 can teach C2 at times 1 or 5, but time 1 is taken by T1, so we schedule it at time 5.  Similarly, C3 is available at times 2 and 3, and T3 is also available at time 3, so we can schedule that class then.

Reduction: Even, Itai, and Shamir use 3SAT.  So we’re given a set X of literals (x1 through xl, and the negation ~x1 through ~xl), and a set D of k clauses (D1 through Dk).  Define pi to be the number of times variable i (so the literal xi or the literal ~xi)  shows up in the formula.  Each variable i will get 5*pi classes denoted Ciab, where a runs from 1 to pi, and b runs from 1 to 5.  There will be 3 hours to schedule the classes.   They organize the teachers for the classes in a widget that looks like this (from the paper, p. 693):

The idea is that the diagonal lines are teachers who have to teach the 2 classes connected by the line (So, C12 and C13 for example) and the crosses are the 2 ways they can teach it (so h2 and h3).  The bottom arrows are teachers who can have 3 hours of availability and 3 classes to teach.  Each variable gets pi teachers who teach Cq3 and Cq4 (where q runs from 1 to pi) during h1 and h2.  If Cq3 is taught at time h1, the variable is treated as being set to positive, otherwise, it’s negative.

We then need to add more jobs to make sure that we make one literal true in each clause.  This is done by creating a teacher with 3 classes (one for each literal in the clause).  If the literal is the qth occurrence of literal xi, the teacher is assigned to class Ciq2 if the literal is true, and Ciq5 if the literal is false.

If there is a satisfiable solution to the SAT instance, the literal that makes each clause true will define a way to set the teacher at time h1 and h2, and that starts a chain reaction that schedules everything.

If there is a feasible timetable, we look at the Ciq3 and Ciq4 classes to see how we have allocated the teachers to those tasks, which tells us how to set the variables to make each clause true.

Difficulty: 9.  I’m having a hard time following all of the classes and teachers here.  I wonder if there is a much easier way to do this if we reduce from some other problem.


Protected: Register Sufficiency

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

Protected: Conjunctive Query Foldability

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

Protected: Additional Key

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

Protected: Prime Attribute Name

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: Internal Macro Data Compression

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

Protected: Polynomial Non-Divisibility

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