\documentclass{article}
\input{6854-preamble}

\begin{document}
\psetnum{8}
\date{2004/11/03}
\collab{Collaborators: \texttt{\{sarahl,pramook\}}}

\begin{pset}
  \begin{problem}
    \begin{subproblem}
      We claim that any feasible subset of jobs can be scheduled in
      order of increasing deadline. Suppose there is a feasible
      schedule that does not have this property. Then there are two
      jobs, $x$ and $y$, with $x$ scheduled before $y$, and $y$'s
      deadline $d_y < d_x$. Then we can swap them. $y$ will now be
      scheduled before $x$. This is feasible for $y$, since $y$'s scheduling
      was feasible before and it is only moved earlier. It is feasible
      for $x$ because $x$ is now finished at the time $y$ originally
      did, which was before $d_y$ and hence $d_x$. We can repeatedly
      swap jobs until there are no more out-of-order jobs.
    \end{subproblem}

    \begin{subproblem}
      We give a dynamic program for computing the fastest-completing
      maximum-weight feasible subset. Define $T(n,W)$ to be the
      shortest time required to complete a schedule of total weight
      $W$ using only the first $n$ jobs. Then, since we either include
      the $n$th job or not,
      \[ T(n,W) = \min\left(T(n-1, W), T(n-1, W - w_n) + p_n\right)\]
      provided that adding job $n$ is feasible, i.e. $T(n-1, W - w_n)
      + p_n \le d_n$. If this inequality does not hold, then $T(n,W) =
      T(n-1,W)$. This gives a dynamic program, along with $T(0,W) =
      T(n, 0) = 0$. It has $\sum w_i$ rows and $n$ columns; since we
      assume the weights are polynomially bounded, their sum is also,
      and so the complexity of the dynamic program is polynomial.
    \end{subproblem}

    \begin{subproblem}
      This gives a fully-polynomial approximation scheme for the
      problem of minimizing lateness penalties. We cannot directly use
      the dynamic program above, since the weights may not be
      polynomially bounded. So we must scale the weights. Let
      $\mathscr{W}$ be the sum of weights, $\mathscr{W} = \sum_i
      w_i$, and let \[K = \frac{\mathscr{W}\epsilon}{n}\] Then we rescale each
      weight by dividing it by $K$ and rounding:
      \[w_i' =
      \floor{\frac{w_i}{K}}\]
      We can then apply the dynamic program described above to find
      the fastest-completing maximum-weight feasible subset of the
      scheduling problem with the rescaled weights $w_i'$. The dynamic
      program table has $\sum w_i'$ rows and $n$ columns, and constant
      time is required to fill in each cell. Recall that \[\sum w_i'=
      \frac{\sum w_i}{\frac{\mathscr{W} \epsilon}{n}} =
      \frac{n \mathscr{W}}{\epsilon \mathscr{W}} = \frac{n}{\epsilon}\]
      so solving the dynamic program requires $n \frac{n}{\epsilon}$
      time. Thus this algorithm has the running time of a
      fully-polynomial approximation scheme.
      
      We can then schedule all jobs that are in the fastest-completing
      maximum-weight feasible subset identified by the dynamic program
      in order of increasing due date (since we have shown that this
      is an optimal solution), and then scheduling the remaining jobs
      in any order (since they cannot be completed in the
      maximum-weight feasible solution, we must incur the lateness
      penalty associated with them in any case, and so it does not
      matter when they are scheduled as long as it is after the
      feasible subset). 
      
      The answer to the dynamic program is not the optimal value,
      however, as we have rounded the weights. Call the weight of the
      maximum-weight subset the dynamic program found $\mathfrak{W}$.
      Note that the error introduced by rounding on $w_i'$ is at most
      $K = \mathscr{W}{\epsilon}$, and so the error introduced over
      all weights is at most $n \mathscr{W}\epsilon$. We rounded down,
      so $\mathfrak{W}$ is less than the optimum $\mathfrak{W}_{opt}$
      by at most $n \mathscr{W} \epsilon$. Consider also the maximum
      weight $\mathfrak{W}'$ obtained if we had rounded \emph{up}
      instead of down. Then we know that $\mathfrak{W'} - n K
       < \mathfrak{W} \le \mathfrak{W_{opt}}$.  So
      $\mathfrak{W'} - \mathfrak{W} < K \mathscr{W}$. Also
      $\mathfrak{W'} \le \mathfrak{W}_{opt}$ since $\mathfrak{W'}$ is
      obtained using rounding. So $\mathfrak{W}_{opt} - \mathfrak{W} <
      K n = \mathscr{W} \epsilon$. This is the amount by which the
      computed weight of the maximum-weight feasible subset is less
      than that of the optimum solution. Since the algorithm incurs
      the lateness penalty for all the jobs not in this subset, if we
      let $X$ be the total lateness penalty obtained by this
      approximation algorithm and $X_{opt}$ be the optimum, we have
      \[ X \le X_{opt} + \mathscr{W} \epsilon \le (1 + \epsilon)
      X_{opt} \]
      and so our algorithm is a fully-polynomial time approximation
      scheme.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      Suppose there are pairs $(x_k, y_k)$ of vertices that must
      be connected. We define the following integer linear program, which is
      essentially $n$ unit-cost flows. Define $f_{ij}^k$ to be the
      indicator random variable indicating whether demand pair $k$'s
      path uses edge $i\to j$. Then we have the following integer
      linear program:

      \begin{align*}
        \forall i,j,k \;\;\; 0 \le f_{ij}^k &\le 1 \\
        \forall i,j \;\;\; \sum_k f_{ij}^k & \le u_{ij} \\
        \forall j,k \;\;\; \sum_{i \neq j} f_{j,i} - \sum_{i \neq j}
        f_{i,j} &= 
        \begin{cases}
          1 & j = x_k \\
          -1 & j = y_k \\
          0 & \text{otherwise}
        \end{cases}
      \end{align*}

      Any feasible solution to this ILP sends one unit of flow along
      along a path from each demand pair's source to sink, thanks to
      the conservation conditions and the requirement that the
      source-sink flow is 1.
    \end{subproblem}

    \begin{subproblem}
      We relax this integer LP to be a normal linear program. Then we
      eliminate the requirement that $f_{ij}^k$ is an integer, and
      simply enforce that it is between 0 and 1.

      The linear program can be solved in polynomial time. The
      solution will be a fractional flow of total value 1 for each of
      the demand pairs: each $f_{ij}^k$ will be between 0 and 1, and
      for fixed $k$ we still have the conservation criterion and the
      enforcement that flow from the source and into the sink is 1. So
      for each $k$ we have a (possibly fractional) flow of value 1
      from source to sink.
    \end{subproblem}

    \begin{subproblem}
      We now perform randomized rounding on the relaxed linear
      program: for each demand pair $k$, we choose one path from the
      source $x_k$ to the sink $y_k$. We choose path $i$ with
      probability equal to the value of the flow through that path in
      the solution to the relaxed LP; since the sum of the flows
      through each path is 1, this defines a probability
      distribution. We claim that each edge has $\bigO{\log n}$
      paths through it. Call the number of paths $P_{ij}$.
      
      First, note that for any edge $i\to j$, the expected number of
      paths through it is $\Exp{P_{ij}} = \sum_k f_{ij}^k$, which is
      necessarily less than 1. To bound the number of paths, we use
      the Chernoff bound, which we can do since the number of paths is
      given by a sum of indicator random variables.

      %Let $\psi = 1 + \log n$.
      Then, by the Chernoff bound,
      \[ \Pr{P_{ij} \ge 1 + \log n} \le 2^{-(1 + \log n)} \]
      since the mean is at most 1. And, using the union bound, since
      there are $n$ edges, the probability that there is any edge with
      more than $1 + \log n$ paths through it is
      \[ n \left( 2^{-(1 + \log n)} \right) = \frac{n}{n} 2^{-1}
      = \nicefrac{1}{2} \]
      
      So the expected number of rounding attempts to be performed with
      guaranteed at most $1 + \log n = \bigO{\log n}$ paths going
      through every edge is 2, a constant. This is certainly
      polynomial time, and the remainder of the algorithm is also
      polynomial, so this proves the claim.
    \end{subproblem}

    \begin{subproblem}
      Suppose now that each edge has capacity $w$.  Then the expected
      number of paths through an edge is $\Exp{P_{ij}} = \sum_k
      f_{ij}^k \le w$. We now consider the probability that the number
      of paths through an edge exceeds $w$ by a factor of $\epsilon$,
      for some $\epsilon < 1$. By the Chernoff bound,
      \[ \Pr{P_i \ge (1 + \epsilon) w} \le e^{-\frac{\epsilon^2 w}{4}}
      \]
      and so the probability that any edge has more than $(1+\epsilon
      w)$ paths is
      \[ n e^{-\frac{\epsilon^2 w}{4}} \]
      We must make this a constant probability, by letting
      \[\epsilon = \left(\frac{\ln n}{w}\right)^{\nicefrac{1}{2}}
      \]
      so that the probability is $n e^{-\frac{\ln n}{4}} =
      e^{-\frac{1}{4}}$, which is a constant, so we can repeat the
      rounding a constant number of times to ensure no edge has more
      than $(1 + \epsilon) w$ paths through it. If $w > \log n$, this
      is $w + \bigO{\sqrt{w\log n}}$, and if $w \le \log n$, this is simply
      $w + \bigO{\log n}$.
      
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      If the answer is ``yes'', then there is a set $B$ of size $k$
      such that every set in $C$ is the union of some subset of $B$.
      There are at most $2^k$ subsets of $B$, so there cannot be more
      than $2^k$ sets in $C$ without having duplicate sets in $C$,
      which is impossible.
    \end{subproblem}

    \begin{subproblem}
      Suppose that for all $S$ in $C$, $x \in S$ if and only if $y \in
      S$. Then we can remove $y$ from all sets in $C$ without changing
      the answer to the set basis problem. For some $S$, suppose first
      that $x \not \in S$. Then $y \not \in S$, so removing $y$ from
      $C$ does not affect $S$. Now suppose $x \in S$. Then $y \in S$
      also. In the basis, $S$ is the union of some $\psi_i \in
      B$. Removing $y$ from $C$ removes it from $S$. But we can also
      remove $y$ from all $\psi_i$ that cover $S$. This does not
      affect the cover, since the same sets will still cover $S$
      without $y$, and $y$ is no longer needed to cover any set. Thus,
      $y$ can be removed from all sets in $C$ and $B$ without changing
      the answer to the set basis problem.
    \end{subproblem}

    \begin{subproblem}
      Consider an instance of the set basis problem. The set $C$
      contains at most $2^k$ sets if the answer is ``yes'', so we know
      that if $C$ contains more than $2^k$ sets, we can immediately
      answer ``no'', and hence we can assume $C$ contains at most
      $2^k$ sets.
      
      We now claim that the sets in $C$ can be reduced to at most
      $2^{2^k}$ elements. The power set of $C$ contains $2^{2^k}$
      families of the $2^k$ sets in $C$. Each element $y$ in a set $S
      \in C$ is in some collection of sets in $S$, which is given by
      one of families in the power set of $C$. So if there are more
      than $2^{2^k}$ elements in the sets of $C$, then by the
      pigeonhole principle there must be some $x$ that is in the same
      family of sets in $C$. So $y$ can be eliminated. This process
      can be repeated to reduce $C$'s sets to at most $2^{2^k}$
      elements.

      Hence, we can simply test assignments of the $2^{2^k}$ elements
      in the sets of $C$ to $k$ sets in $B$. This can be done in less
      than $k 2^{2^{2^k}}$ time\footnote{This bound is presumably not
      at all tight.}, which is a function of $k$, plus time polynomial
      in the problem size to identify and remove redundant elements. 
    \end{subproblem}
  \end{problem}

  \begin{problem}
    Consider an instance of $MAX-SAT$ with treewidth $k$. We use
    essentially the same algorithm as for $SAT$ to show that it is
    fixed-parameter tractable. We create the graph where vertices
    represent variables, and two vertices are connected if two
    variables share a clause; this is the graph that we assume has
    treewidth $k$. We then proceed to eliminate variables using the
    optimal elimination ordering on the graph.
    
    We maintain for each clause a truth table, augmented for each
    assignment of variables with the number of reduced-clauses
    (clauses that were previously eliminated and reduced into the
    current clause, plus the current clause) satisfied by that
    assignment. So in the initial case, this is simply 1 for every
    assignment that satisfies the clause, and 0 otherwise.
    
    
    Let $x$ be the variable being removed. We find all clauses
    involving $x$ and enumerate all possible assignments of variables
    for that clause. We can build a truth table for the combination of
    all clauses involving $x$ essentially by joining the truth tables
    we have for each clause. There are at most $k$ variables involved,
    since this is the degree of the $x$ vertex, so the truth table
    size is $2^k$. We combine these into a new clause of at most $k$
    variables. Rather than simply identifying settings of the
    variables such that some $x$ makes all clauses true (as we do in
    the $SAT$ FPT algorithm), we must consider the
    reduced-clauses-satisfied. For each combination of the other
    variables involved ($y$, $z$, \ldots), we choose the value of $x$
    that maximizes the sum of the reduced-clauses-satisfied for that
    combination of the other variables. We then add that combination
    to the truth table with the maximized sum of
    reduced-clauses-satisfied we found, and add a tag indicating which
    assignment of $x$ we chose. Once we consider each combination of
    the variables, we have eliminated the variable $x$ and built up
    the augmented truth table for the new clause.
    
    We apply this procedure for each variable until we have eliminated
    all variables. Since we choose the maximum sum of
    reduced-clauses-satisfied at each stage, the final reduction will
    give the maximum number of satisfiable clauses, and the tags
    attached will indicate the necessary assignments of each of the
    variables.

    Note that the processing time required to process each clause
    elimination is proportional to the size of the truth table, which
    we showed above was $2^k$. There are $n$ variables to be
    eliminated, so the runtime is $\bigO{n 2^k}$, indicating that the
    problem is fixed-parameter tractable.
  \end{problem}

  \begin{problem}
    12 hours or so.
  \end{problem}
\end{pset}
\end{document}

% LocalWords:  Chernoff treewidth polynomially
