# Commits

committed d4023ac

approximation algorithms

• Participants

# File doc/articles

+http://www.cs.princeton.edu/theory/index.php/Main/ApproxSeminar
+http://cs.haifa.ac.il/courses/approx_algo/
+http://www.ti.inf.ethz.ch/ew/courses/ApproxAlgsSemHS09/
+http://www.math.neu.edu/bhmn/mitchell11.html
+http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=11241
+http://www.cs.huji.ac.il/~yair/approx/approx-seminar.html
+http://business.rutgers.edu/events/2011/09/28/seminar-multi-dimensional-approximation-algorithms-capacity-expansion-problems
+

# File hw/ch01.tex

+\documentclass{homework}
+
+\lhead{TCSS 600}
+\chead{Approximation Algorithms}
+\rhead{Chapter 1}
+
+\begin{document}
+\begin{enumerate}
+\item[1.1] Give a factor $1/2$ algorithm for the following:
+\begin{problem}
+Given a directed graph $G = (V, E)$, pick a maximum cardinality set of edges from $E$ so that the resulting subgraph is acyclic.
+\end{problem}
+{\bf Algorithm:} \\*
+\begin{enumerate}
+\item[1.] Number the vertices from 1 to $|V|$.
+\item[2.] Each directed edge can be considered an ordered pair $(i, j)$ with $1 \leq i, j \leq |V|$. Loop through each edge, forming the two sets $A = \{(i, j) \in E \mid i < j\}$ and $B = \{e = (i, j) \in E \mid i > j\}$.
+\item[3.] Output the larger of $A$ and $B$. If they have the same size, output $A$.
+\end{enumerate}
+This algorithm gives a factor $1/2$ algorithm to the acyclic subgraph problem.
+
+\begin{proof}
+Without loss of generality, assume $A$ were larger. Suppose $A \subseteq E$ had a cycle, let $\sigma$ be this cycle, and consider the set of edges comprising $\sigma$, $\{(k, l) \mid k < l\} \subseteq A$. Let $k'$ be the smallest first coordinate. Since $\sigma$ is a cycle, there must be some edge $(l', k') \in \sigma$. However, since $\sigma \subseteq A$, $l'$ must be less than $k'$, a contradiction. Therefore, $A$ does not contain a cycle. Since $A$ is an acyclic subgraph and is at least half the size of $E$, the maximum cardinality set of edges from $E$ is bounded below by $|A|/2$.
+\end{proof}
+
+ Furthermore, this particular lower bounding scheme cannot be improved, and the factor $1/2$ is tight.
+\begin{proof}
+First, consider any bi-directional complete graph and any numbering of the vertices. The algorithm produces a uni-directional complete graph, comprised of half the edges. Furthermore if $(i, j) \not \in A$, the algorithm's acyclic subgraph, then $(i, j) \in A$. Therefore, the addition of any edge not in $A$ creates a cycle $\{(i, j), (j, i)\}$ of order 2. Hence $A$ is a maximum cardinality acyclic subgraph of size exactly $1/2$ of $E$.
+
+Second, the factor $1/2$ can be shown to be nearly tight, as follows. Consider any cyclic graph of even order, say $2n$. The algorithm may label the vertices as $(1, 3, 5,..., 2n-1, 2n, 2n-2, 2n-4, ..., 6, 4, 2)$. Sets $A$ and $B$ are both of size $n$, whereas the maximum acyclic graph is of size $2n-1$.
+\end{proof}
+
+\item[1.2] Design a factor 2 approximation algorithm for the problem of finding a minimum cardinality maximal matching in an undirected graph.
+
+{\bf Algorithm:}
+
+\begin{enumerate}
+\item[1.] Greedily select edges until a maximal matching, $M$, is found.
+\item[2.] Output $M$.
+\end{enumerate}
+This is a factor 2 algorithm for finding the minimum cardinality maximal matching.
+\begin{proof}
+First note that if $M$ is a maximal matching and $\tilde M$ is the maximum matching, that every edge $e$ of $\tilde M$ has at least one of its endpoint in the set vertices of $M$. If not, there would be an edge, $e'$, that could legally increase the matching $M$, violating maximality of $M$. Therefore, all maximal matchings are at least half the size of the maximum matching. Also, note, that maximal matchings are no more than the maximum matching, by definition. \\*
+
+Therefore, a minimum cardinality maximal matching, $M_c$ is at least half the size of the maximum matching, $\tilde M$. Since $\frac{1}{2} \tilde M \leq M_c \leq M \leq \tilde M$, the output $M$ can be no more than twice the size of a minimum cardinality maximal matching, and thus provides a factor 2 approximation to the minimum cardinality maximal matching.
+\end{proof}
+
+\end{enumerate}
+\end{document}

# File hw/ch02.tex

+\documentclass{homework}
+
+\lhead{TCSS 600}
+\chead{Approximation Algorithms}
+\rhead{Chapter 2}
+
+\begin{document}
+\begin{enumerate}
+\item[2.1] Given an undirected graph $G = (V, E)$, the {\em cardinality maximum cut problem} asks for a partition of $V$ into sets $S$ and $\bar{S}$ so that the number of edges running between these sets is maximized. Consider the following greedy algorithm for this problem. Here $v_1$ and $v_2$ are arbitrary vertices in $G$, and for $A \subset V$, $d(v, A)$ denotes the number of edges running between vertex $v$ and set $A$.
+
+{\bf Algorithm:}
+\begin{enumerate}
+\item[1.] Initialization:
+
+$A \leftarrow \{v_1\}$ \\*
+$B \leftarrow \{v_2\}$
+\item[2.] For $v \in V - \{v_1, v_2\}$ do:
+
+if $d(v, A) \geq d(v, B)$ then $B \leftarrow B \cup \{v\}$, \\*
+else $A \leftarrow A \cup \{v\}$.
+\item[3.] Output $A$ and $B$.
+\end{enumerate}
+Show that this is a factor $\frac{1}{2}$ approximation algorithm and give a tight example. Give examples of graphs for which this upper bound is as bad as twice $OPT$.
+\begin{proof}
+Initially, $A = \{v_1\}$ and $B = \{v_2\}$. As a matter of notation, enumerate the remaining vertices in $V$ as $v_3, v_4, \dots v_n$ in the order they are selected by the algorithm. Let $A_i$ and $B_i$ denote sets $A$ and $B$, respectively, after vertex $i$ has been selected by the algorithm. Let $S$ and $\bar{S}$ denote the set of vertices in the optimal set and its complement, respectively, and let $S_i$ and $\bar{S}_i$ denote the intersections $S \cap (A_i \cup B_i)$ and $\bar{S} \cap (A_i \cup B_i)$.
+
+When the algorithm completes, it will have added each vertex, $v_j$, to either $A$ or $B$, and some portion of the edges incident with $v_j$ will have counted toward the value of $d(A, B)$. As well, no edge contributes twice to the value $d(A, B)$ more than once, since only edges of the form $e_{ij} = (v_i, v_j)$ with $i < j$ are considered. More precisely, $d(A, B) = \sum_{i} \max\{d(v_{i+1}, A_i), d(v_{i+1}, B_i)\}$. Furthermore, $A_i \cap B_i = \emptyset$, $d(v_{i+1}, A_i) + d(v_{i+1}, B_i)\} \geq d(v_{i+1}, A_i \cup B_i)$ and $S_i \subseteq A_i \cup B_i$. Therefore, we have the following:
+\begin{align*}
+d(A, B) &=     \sum_{i} \max\{d(v_i, A_{i-1}), d(v_i, B_{i-1})\} \\
+        &\geq  \sum_{i} \frac{1}{2} d(v_i, A_{i-1} \cup B_{i-1}) \\
+        &=     \frac{1}{2} \sum_{i} d(v_i, S_{i-1} \cup \bar{S}_{i-1}) \\
+        &\geq  \frac{1}{2} \left(\sum_{v_i \in \bar{S}_i} d(v_i, S_{i-1}) + \sum_{v_i \in S_i} d(v_i, \bar{S}_{i-1})\right) \\
+        &=     \frac{1}{2} \cdot OPT
+\end{align*}
+
+The family of graphs in Figure~\ref{fig:cone} provides tight examples for the factor $\frac{1}{2}$.
+\begin{figure}[htbl]
+\begin{center}
+\begin{tikzpicture}
+\draw (0,2) -- (-1.5, 0) -- (0, -2);
+\draw (0,2) -- (-1, 0) -- (0, -2);
+\draw (0,2) -- (-0.5, 0) -- (0, -2);
+\draw (0,2) -- (0, 0) -- (0, -2);
+\draw (0,2) -- (0.5, 0) -- (0, -2);
+\draw (0,2) -- (1, 0) -- (0, -2);
+\draw (0,2) -- (1.5, 0) -- (0, -2);
+\draw[fill=black] (0,2) circle (0.1) node[above]{$v_1$};
+\draw[fill=white] (0,-2) circle (0.1) node[below]{$v_2$};
+\draw[fill=white] (-1.5,0) circle (0.1) node{};
+\draw[fill=black] (-1,0) circle (0.1) node{};
+\draw[fill=white] (-0.5,0) circle (0.1) node{};
+\draw[fill=black] (0,0) circle (0.1) node{};
+\draw[fill=black] (0.5,0) circle (0.1) node{};
+\draw[fill=white] (1,0) circle (0.1) node{};
+\draw[fill=black] (1.5,0) circle (0.1) node{};
+\end{tikzpicture}
+\end{center}
+\caption{Tight examples for the factor $\frac{1}{2}$ greedy algorithm}
+\label{fig:cone}
+\end{figure}
+Selecting $v_1$ and $v_2$ as the top and bottom vertices, we guarantee that only half the edges, no matter the choice of $A$ or $B$ for vertex $v_i$, count toward $d(A, B)$. However, the optimal solution selects all the edges, since we can choose $S$ to be the top and bottom vertices, and $\bar{S}$ as the remaining.
+\end{proof}
+
+\item[2.6] Consider the following problem:
+\begin{problem}
+Given an undirected graph $G = (V, E)$, color its vertices with the minimum number of colors so that the two end-points of each edge receive distinct colors.
+\end{problem}
+\begin{enumerate}
+\item[1.] Give a greedy algorithm for coloring $G$ with $\Delta + 1$ colors, where $\Delta$ is the maximum degree of a vertex in $G$.
+\end{enumerate}
+\end{enumerate}
+\end{document}

# File hw/ch12.tex

+\documentclass{homework}
+
+\lhead{TCSS 600}
+\chead{Approximation Algorithms}
+\rhead{Chapter 12}
+
+\begin{document}
+\begin{enumerate}
+\item[12.1] Show that the dual of the dual of a linear program is the original program itself.
+
+\begin{proof}
+Although not vital to the formal proof, the following layout of the primal and dual programs highlights the relationship between them:
+\begin{figure}[htbl]
+\begin{center}
+\begin{tabular}{ c | c  c  c  c  c | c | c }
+          & $x_1$    & $x_2$    & $x_3$    & $\cdots$ & $x_n$    &          &        \\ \hline
+ $y_1$    & $a_{11}$ & $a_{12}$ & $a_{13}$ & $\cdots$ & $a_{1n}$ & $\geq$   & $b_1$  \\
+ $y_2$    & $a_{21}$ & $a_{12}$ & $a_{13}$ & $\cdots$ & $a_{1n}$ & $\geq$   & $b_2$  \\
+ $y_3$    & $a_{31}$ & $a_{12}$ & $a_{13}$ & $\cdots$ & $a_{1n}$ & $\geq$   & $b_3$  \\
+ $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$ &          & $\vdots$ & $\vdots$ & $\vdots$ \\
+ $y_m$    & $a_{11}$ & $a_{12}$ & $a_{13}$ & $\cdots$ & $a_{1n}$ & $\geq$   & $b_m$  \\ \hline
+          & $\leq$   & $\leq$   & $\leq$   & $\cdots$ & $\leq$   &          & $\max \sum_{i=1}^{m}b_i y_i$ \\ \hline
+          & $c_1$    & $c_2$    & $c_3$    & $\cdots$ & $c_m$    & $\min \sum_{j=1}^{n}c_j x_j$ &
+\end{tabular}
+\end{center}
+\end{figure}
+
+The primal program, specifically, is of the form
+\begin{align*}
+\mbox{minimize} \hspace{4mm} & \sum_{j=0}^n c_j x_j \\
+\mbox{subject to} \hspace{4mm} & \sum_{j=0}^n a_{ij}x_j \geq b_i \\
+\mbox{and} \hspace{4mm} & x_j \geq 0
+\end{align*}
+The operation of taking the dual of a linear program transforms this problem to the dual program:
+\begin{align*}
+\mbox{maximize} \hspace{4mm} & \sum_{i=0}^n b_i y_i \\
+\mbox{subject to} \hspace{4mm} & \sum_{i=0}^n a_{ij}y_i \leq c_j \\
+\mbox{and} \hspace{4mm} & y_i \geq 0
+\end{align*}
+In order to apply the dual operation to the dual linear program, we must formulate the dual as a primal program. That is, a minimization constrained from below:
+\begin{align}
+\label{eqn:dual-as-primal}
+\mbox{minimize} \hspace{4mm} & \sum_{i=0}^n -b_i y_i \notag \\
+\mbox{subject to} \hspace{4mm} & \sum_{i=0}^n -a_{ij}y_i \geq -c_j \\
+\mbox{and} \hspace{4mm} & y_i \geq 0 \notag
+\end{align}
+Applying the dual operation to LP~(\ref{eqn:dual-as-primal}) and labeling the dual variables as $x_j$, we get:
+\begin{align*}
+\mbox{maximize} \hspace{4mm} & \sum_{j=0}^n -c_j x_j \\
+\mbox{subject to} \hspace{4mm} & \sum_{j=0}^n -a_{ij}x_j \leq -b_i \\
+\mbox{and} \hspace{4mm} & x_j \geq 0
+\end{align*}
+Reformulating this dual as a primal program, we arrive at the original.
+\end{proof}
+
+\item[12.2] Show that any minimization program can be transformed into an equivalent program in standard form.
+\begin{proof}
+First, note that standard form is:
+\begin{align}
+\mbox{minimize} \hspace{4mm} & \sum_{j=1}^n c_j x_j \notag \\
+\mbox{subject to} \hspace{4mm} & \sum_{j=1}^n a_{ij}x_j \geq b_i \label{eqn:relconstraint} \\
+\mbox{and} \hspace{4mm} & x_j \geq 0 \label{eqn:varconstraint}
+\end{align}
+
+
+\begin{enumerate}
+\item[Case 1.] Assume a variable constraint~(\ref{eqn:varconstraint}) had the form $x_j \geq k$:
+
+Subtract $k$ from both sides and perform the substitution $x_j \mapsto x_j + k$ throughout. This would transform the non-standard constraint $x_j \geq k$ to standard form. However, constraints in~\ref{eqn:relconstraint} would be affected. Simplify each expression such expression in~(\ref{eqn:relconstraint}) by isolating the constants. Perform the relabeling $b_i - a_{ij}k \mapsto b_i$.
+
+\item[Case 2.] Assume a variable constraint~(\ref{eqn:varconstraint}) had the form $x_j \leq k$:
+
+Simply multiply both sized of the $j^{th}$ variable constraint by $-1$ and perform the relabelings $-x_j \mapsto x_j$ and $-a_{ij} \mapsto a_{ij}$ throughout. Then apply Case 1 to the constraint $x_j \geq -k$.
+
+\item[Case 3.] Assume a relation constraint~(\ref{eqn:relconstraint}) had the form $\sum_{j=1}^n a_{ij} x_j \leq b_i$:
+
+Simply multiply both sides of the $i^{th}$ relation constraint by $-1$ and perform the relabelings $-a_{ij} \mapsto a_{ij}$ and $-b_i \mapsto b_i$.
+
+\item[Case 4.] Assume a relation constraint~(\ref{eqn:relconstraint}) had the form $\sum_{j=1}^n a_{ij} x_j = b_i$:
+
+Add another constraint and reformulate the equality as two inequalities of the form $\sum_{j=1}^n a_{ij} x_j \geq b_i$ and $\sum_{j=1}^n a_{ij}' x_j \leq b_i'$ where $a_{ij}' = a_{ij}$ and $b_i' = b_i$ inserting them as the $(i+1)^{th}$ set of expressions. Apply Case 3 to the second inequality.
+
+\item[Case 5.] Assume a variable constraint~(\ref{eqn:varconstraint}) had the form $x_j = k$:
+
+Add another variable $x_j'$ and reformulate the equality as two inequalities of the form $x_j \geq k$ and $x_j' \leq k$. Furthermore, add a whole set of relation constraints $\sum_{j=1}^n a_{ij} x_j' \geq b_i$ identical to the existing constraints except having $x_j$ replaced by $x_j'$. Apply Case 1 and 2, as required.
+\end{enumerate}
+\end{proof}
+\end{enumerate}
+\end{document}

# File hw/ch13.tex

+\documentclass{homework}
+
+\lhead{TCSS 600}
+\chead{Approximation Algorithms}
+\rhead{Chapter 13}
+
+\begin{document}
+\begin{enumerate}
+\item[13.2] Give an example in which the dual solution $price(e)$ for each element $e$ computed by algorithm 2.2 overpacks some sets, $S$, by a factor of essentially $H_{|S|}$.
+
+\begin{proof}
+Consider the following sets:
+
+\begin{figure}[htbl]
+\begin{center}
+\begin{tikzpicture}
+\draw[fill=black] (0,0) circle (0.1){};
+\draw[fill=black] (0,1) circle (0.1){};
+\draw[fill=black] (0,2) circle (0.1){};
+\draw[fill=black] (0,3) circle (0.1){};
+\draw[fill=black] (0,4) circle (0.1){};
+\draw[fill=black] (1,0) circle (0.1){};
+\draw[fill=black] (1,1) circle (0.1){};
+\draw[fill=black] (1,2) circle (0.1){};
+\draw[fill=black] (1,3) circle (0.1){};
+\draw[fill=black] (1,4) circle (0.1){};
+\draw[fill=black] (2,1) circle (0.1){};
+\draw[fill=black] (2,2) circle (0.1){};
+\draw[fill=black] (2,3) circle (0.1){};
+\draw[fill=black] (2,4) circle (0.1){};
+\draw[fill=black] (3,2) circle (0.1){};
+\draw[fill=black] (3,3) circle (0.1){};
+\draw[fill=black] (3,4) circle (0.1){};
+\draw[fill=black] (4,3) circle (0.1){};
+\draw[fill=black] (4,4) circle (0.1){};
+\draw[fill=black] (5,4) circle (0.1){};
+
+\draw (0,2) ellipse (0.4 and 2.5);
+\draw (0,5) node{1};
+\draw (1,2.5) ellipse (0.4 and 2);
+\draw (1,5) node{1};
+\draw (2,3) ellipse (0.4 and 1.5);
+\draw (2,5) node{1};
+\draw (3,3.5) ellipse (0.4 and 1);
+\draw (3,5) node{1};
+\draw (4,4) ellipse (0.3 and 0.5);
+\draw (4,5) node{1};
+
+\draw (2.5,4) ellipse (3 and 0.4);
+\draw (6,4) node{$\frac{6}{5} + \epsilon$};
+\draw (2,3) ellipse (2.5 and 0.4);
+\draw (5,3) node{$\frac{5}{4} + \epsilon$};
+\draw (1.5,2) ellipse (2 and 0.4);
+\draw (4,2) node{$\frac{4}{3} + \epsilon$};
+\draw (1,1) ellipse (1.5 and 0.4);
+\draw (3,1) node{$\frac{3}{2} + \epsilon$};
+\draw (0.5,0) ellipse (1 and 0.4);
+\draw (2,0) node{$2 + \epsilon$};
+\end{tikzpicture}
+\end{center}
+\caption{An example where some sets $S$ are overpacked by a factor of essentially $H_{|S|}$}
+\end{figure}
+In the optimal solution, only the horizontal sets would be picked. The greedy algorithm would select each of the vertical sets, then each of the horizontal sets. To the $i^{th}$ horizontal set (of size $|S| = i+1$, the vertical sets would supply $\sum_{j=1}^i \frac{1}{j}$ in price. The last element would be added with price $\frac{i+1}{i} + \epsilon$. Therefore, the $i^{th}$ horizontal set would be overpacked by $H_{i-1}$ which is essentially $H_{|S|}$.
+\end{proof}
+\end{enumerate}
+\end{document}

# File hw/ch14.tex

+\documentclass{homework}
+
+\lhead{TCSS 600}
+\chead{Approximation Algorithms}
+\rhead{Chapter 14}
+
+\begin{document}
+\tikzstyle{every node}=[circle, draw, fill=black!50, inner sep=0pt, minimum width=4pt]
+
+\begin{enumerate}
+\item[14.1] Modify Algorithm 14.1 so that it picks all sets that are nonzero in the fractional solution. Show that the algorithm also achieves a factor of $f$.
+\begin{proof}
+Consider the redefined algorithm:
+\\\\*
+{\bf Redefined algorithm}
+\begin{enumerate}
+\item[1.] Find an optimal solution to the LP-relaxation.
+\item[2.] Pick all sets $S$ for which $x_S > 0$ in this solution.
+\end{enumerate}
+The primal solution is one that minimizes $\sum_{S \in \mathcal{S}} c(S) x_S$. By complementary slackness, we either have $x_S = 0$ for sets that aren't picked or $\sum_{e \in S} y_e = c(S)$ for sets that are picked. Let $\mathcal{T}$ be the collection of sets that are picked and $x_S^*$ and $y_e^*$ be the values of $x_S$ and $y_e$ for each set $S$ and element $e$ in an optimal solution. Then
+
+\begin{align*}
+OPT_f &= \sum_{S \in \mathcal{S}'} c(S) x_S^* \\
+  &= \sum_{S \in \mathcal{S}'} \left(\sum_{e \in S} y_e^* \right) x_S^* \\
+  &= \sum_{S \in \mathcal{S}'} \sum_{e \in S} x_S^* y_e^* \\
+  &= \sum_e \left( \sum_{\substack{S \in \mathcal{S}' \\ e \in S}} x_S^* \right) y_e^*
+\end{align*}
+In the algorithm, for each $S \in \mathcal{T}$, $x_S^*$ is rounded up to 1. Therefore, we have:
+\begin{align*}
+OPT_f &= \sum_e \left( \sum_{\substack{S \in \mathcal{S}' \\ e \in S}} x_S^* \right) y_e^* \\
+  &\leq \sum_{e} \left( \sum_{\substack{S \in \mathcal{S}' \\ e \in S}} 1 \right) y_e^* \\
+  &= \sum_e f(e) y_e^*
+\end{align*}
+where $f(e)$ is the frequency of element $e$. Letting $f$ represent the most frequent element, and since $OPT_f \leq OPT$, we have:
+\begin{equation*}
+OPT_f \leq \sum_e f(e) y_e^* \leq \sum_e f y_e^* = f \sum_e y_e^* = f \cdot OPT_f \leq f \cdot OPT
+\end{equation*}
+\end{proof}
+
+\item[14.4] Give a non-bipartite tight example for the half-integrality-based algorithm for the weighted vertex cover.
+\begin{proof}
+Consider any cycle with $4n$ vertices with a dividing edge'':
+\begin{figure}[htbl]
+\begin{center}
+\begin{tikzpicture}
+\draw (0,-1) -- (0,1);
+\draw \foreach \x in {0,45,90,135,180,225,270,315}
+{
+  (\x:1) node{} -- (\x+45:1)
+};
+\end{tikzpicture}
+\end{center}
+\caption{A non-bipartite, tight example for half-integrality rounding}
+\end{figure}
+First, since a cycle of odd order exists within the graph, no bipartite labeling exists. Since each edge in the even cycle must be covered, then the optimal integral solution would choose $2n$ vertices, as long as that selection chose a vertex incident with the dividing edge. The optimal fractional solution would choose each vertex by $\frac{1}{2}$ so that each edge would be fully covered with a cost of $2n$. However, rounding the LP-relaxation would costs $4n$, hence providing a tight-example to the half-integrality-based algorithm.
+\end{proof}
+
+\item[14.5] Give a polynomial time algorithm for the following problem. Given a graph $G$ with nonnegative vertex weights and a valid, though not necessarily optimal, coloring of $G$, find a vertex cover of weight $\leq (2 - \dfrac{2}{k}) OPT$, where $k$ is the number of colors used.
+
+\begin{proof}
+<only some ideas>
+\begin{itemize}
+\item Note that at least $\frac{1}{k}$ of the vertices have been colored by the color that occurs most frequently.
+\item We can select the vertices with the most popular color with value 1 and remove them from the graph. The remaining graph will have no more than $1- \frac{1}{k}$ vertices.
+\item The remaining vertices can be treated as a subgraph and optimization can be applied to this subgraph. We can apply LP-rounding to this reduced set of vertices.
+\item Maybe some sort of iterative removal based on colors.
+\end{itemize}
+\end{proof}
+
+\item[14.6] Give a counterexample to the following claim. A set cover instance in which each element is in exactly $f$ sets has a (1/$f$)-integral optimal fractional solution.
+\begin{proof}
+Consider a tetrahedron where vertices are considered elements and faces are considered sets. Then $f = 3$ since each vertex belongs to three faces. If the cost of three of the faces is 1 and the fourth face has cost $\frac{3}{2} + \epsilon$, we have LP~\ref{eqn:tetra}.
+\begin{alignat}{4}
+\label{eqn:tetra}
+\mbox{minimize} \hspace{4mm} & 3x_1 & &+ (\frac{3}{2} + \epsilon) x_2 & & \notag \\
+ & \mbox{  } 3x_1 & &      & & \geq 1 \\
+ & \mbox{  } 2x_1 & &+ x_2 & & \geq 1 \notag \\
+ & \mbox{  } x_1, & &  x_2 & & \geq 0 \notag
+\end{alignat}
+Since extreme points of Linear Programs are at vertices and edges of the polyhedron of feasible solutions, if they exist, it suffices to check the objective function at $(\frac{1}{2}, 0)$ and $(\frac{1}{3},\frac{1}{3})$. The first point elicits $\frac{3}{2}$ while the second point elicits $\frac{3}{2} + \frac{1}{3} \epsilon$. Therefore, the optimal solution selects three of the faces with a value of $\frac{1}{2}$, yet every element has frequence $f = 3$.
+\end{proof}
+\end{enumerate}
+\end{document}

# File hw/ch15.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{fancyhdr}
+\usepackage{graphicx}
+
+\pdfpagewidth 8.5in
+\pdfpageheight 11in
+
+\setlength\topmargin{0in}
+\setlength\headheight{0.25in}
+\setlength\headsep{0.25in}
+\setlength\textheight{8.25in}
+\setlength\textwidth{6.5in}
+\setlength\oddsidemargin{0in}
+\setlength\evensidemargin{0in}
+\setlength\parindent{0.25in}
+\setlength\parskip{0.25in}
+
+\pagestyle{fancyplain}
+
+\lhead{TCSS 600}
+\chead{Approximation Algorithms}
+\rhead{Chapter 1}
+
+%%\newcommand{\yields}{\Rightarrow_G^*}
+
+\newtheorem{theorem}{Theorem}
+\newtheorem{proposition}{Proposition}
+\newtheorem{lemma}{Lemma}
+\newtheorem{fact}{Fact}
+\newtheorem{problem}{Problem}
+
+\begin{document}
+\begin{enumerate}
+\item[12.1] Show that the dual of the dual of a linear program is the original program itself.
+
+{\bf Proof:} \\*
+First, the primal program
+$\left( \begin{array}{ccc} +a & b & c \\ +d & e & f \\ +g & h & i \end{array} \right)$
+\end{enumerate}
+\end{document}

# File pres/abstract.sty

+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%  		UW Thesis abstract style file
+%%		  for separate abstract page
+%%			   by
+%%		       Yvonne Nagel
+%%		      Jan. 11, 1995
+%%		Revised May, 1998 by Darren Parker
+%% 		   to force double spacing
+%%  		See accompanying file, abstract.tex
+%%		   for usage instructions.
+%%	     To remove pagenumbers, put \thispagestyle{empty}
+%%		in abstract.tex
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\oddsidemargin 0.5in \evensidemargin 0.6in
+\marginparwidth 40pt \marginparsep 10pt
+\topmargin 0pt \headsep 0in
+\textheight 7.8in \textwidth 5.60in
+\parindent 0pt
+\brokenpenalty=10000
+\font\Bold=cmbx10 scaled \magstep2
+\renewcommand{\baselinestretch}{1.75}
+%\renewcommand{\baselinestretch}{1.75}  % (for wider spacing)
+%% Redefine the title:
+
+\def\@maketitle{%\newpage
+ \null
+ \begin{center}
+ {\Bold \@title \par} \vskip 1.5em
+ {\large \lineskip .5em
+\begin{tabular}[t]{c}\@author
+ \end{tabular}\par}
+ \vspace{.25in}
+ Under the supervision of \professor \\
+ At the University of Washington Tacoma \\
+ \end{center}
+ \par
+}
+

# File pres/abstract.tex

+\documentclass[12pt]{article}
+\usepackage{abstract}
+
+\title{COMBINATORIAL AND GRAPH ALGORITHMS}
+
+\author{Eric Johnson}
+\def\professor{Associate Professor Donald Chinn}
+\begin{document}
+
+\maketitle
+\thispagestyle{empty}
+
+\noindent {\bf Abstract }
+
+The Set Cover problem seeks to find from a collection of sets $\mathcal{S} = \{S_1, S_2, ..., S_k\}$ of a finite universe $U = \{e_1, e_2, ..., e_n\}$, a minimum cover'' of $U$ -- the minimum number of sets needed from $\mathcal{S}$ whose union is $U$. In 1972, this problem was shown to be NP-Complete. The Set Cover problem and its weighted generalization has since played a key role in the development of fundamental techniques in the field of approximation algorithms. Using Set Cover as a common thread, we provide an overview of LP-duality, approximation hardness and the integrality gap, LP-rounding, and the Primal-Dual schema. We end by briefly discussing results of the application of the Primal-Dual schema and LP-rounding to Integer Multicommodity Flow in Trees and Demanded Multicommodity Flow.
+
+\thispagestyle{empty}
+\end{document}

# File pres/approximation-algorithms-abstract.tex

+\documentclass[11pt]{article}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{fancyhdr}
+\usepackage{graphicx}
+
+\pagestyle{fancyplain}
+
+\lhead{TCSS 600}
+\chead{Approximation Algorithms Presentation}
+\rhead{December 9, 2011}
+
+%%\newcommand{\yields}{\Rightarrow_G^*}
+
+\newtheorem{theorem}{Theorem}
+\newtheorem{proposition}{Proposition}
+\newtheorem{lemma}{Lemma}
+\newtheorem{fact}{Fact}
+\newtheorem{problem}{Problem}
+
+\begin{document}
+\begin{enumerate}
+\item[1.1] Give a factor $1/2$ algorithm for the following:
+\begin{problem}
+Given a directed graph $G = (V, E)$, pick a maximum cardinality set of edges from $E$ so that the resulting subgraph is acyclic.
+\end{problem}
+{\bf Algorithm:} \\*
+First, number the vertices from 1 to $|V|$. Each directed edge is mapped to an ordered pair of the form $(i, j)$ with $1 \leq i, j \leq |V|$. Consider the subsets $A = \{(i, j) \in E \mid i < j\}$ and $B = \{e = (i, j) \in E \mid i > j\}$. One of them is larger. Without loss of generality, suppose $A$ is this larger set (merely reverse the labeling of $V$, otherwise). \\*
+
+Suppose $A \subseteq E$ had a cycle, let $\sigma$ be this cycle, and consider the set of edges comprising $\sigma$, $\{(k, l) \mid k < l\} \subseteq A$. Let $k'$ be the smallest first coordinate. Since $\sigma$ is a cycle, there must be some edge $(l', k') \in \sigma$. However, since $\sigma \subseteq A$, $l'$ must be less than $k'$, a contradiction. Therefore, $A$ does not contain a cycle. Since $A$ is an acyclic subgraph and is at least half the size of $E$, the maximum cardinality set of edges from $E$ is bounded below by $|A|/2$. \\*
+
+This algorithm gives a factor $1/2$ algorithm to the acyclic subgraph problem. Furthermore, this particular lower bounding scheme cannot be improved, and the factor $1/2$ is tight. \\*
+
+First, the lower bounding scheme cannot be improved. Consider any bi-directional complete graph and any numbering of the vertices. The algorithm produces a uni-directional complete graph, comprised of half the edges. Furthermore if $(i, j) \not \in A$, the algorithm's acyclic subgraph, then $(i, j) \in A$. Therefore, the addition of any edge not in $A$ creates a cycle $\{(i, j), (j, i)\}$ of order 2. Hence $A$ is a maximum cardinality acyclic subgraph of size exactly $1/2$ of $E$. \\*
+
+Second, the factor $1/2$ can be shown to be nearly tight, as follows. Consider any cyclic graph of even order, say $2n$. The algorithm may label the vertices as $(1, 3, 5,..., 2n-1, 2n, 2n-2, 2n-4, ..., 6, 4, 2)$. Sets $A$ and $B$ are both of size $n$, whereas the maximum acyclic graph is of size $2n-1$. \\*
+
+\item[1.2] Design a factor 2 approximation algorithm for the problem of finding a minimum cardinality maximal matching in an undirected graph.
+
+{\bf Algorithm:} \\*
+First note that if $M$ is a maximal matching and $\tilde M$ is the maximum matching, that every edge $e$ of $\tilde M$ has at least one of its endpoint in the set vertices of $M$. If not, there would be an edge, $e'$, that could legally increase the matching $M$, violating maximality of $M$. Therefore, all maximal matchings are at least half the size of the maximum matching. Also, note, that maximal matchings are no more than the maximum matching, by definition. \\*
+
+Therfore, greedily select edges until a maximal matching, $M$, is found. A maxim. Since the minimum cardinality maximal matching is a maximal matching, it must be at least half the size of $\tilde M$. Hence, $M$ is at most twice the size of the minimum cardinality maximal matching and, thus, this algorithm provides a factor 2 algorithm for finding the minimum cardinality maximal matching. \\*
+
+\item[1.7] Let $A$ be a finite poset. Show that the size of the longest chain equals the size of the smallest antichain cover.
+
+\item[1.8] Let $A$ be a finite poset. Show that the size of the longest antichain equals the size of the smallest chain cover.
+\end{enumerate}
+\end{document}

# File pres/approximation-algorithms-presentation.tex

+\documentclass[mathserif]{beamer}
+\usepackage{mathptmx}
+\usepackage{eulervm}
+\usepackage{helvet}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amsthm}
+\usepackage{tikz}
+\usetikzlibrary{shapes}
+
+\setbeamertemplate{navigation symbols}{}
+
+\usetheme{Antibes}
+\usecolortheme{uw}
+\pgfdeclareimage[height=0.8cm,width=2.2cm]{uw-logo}{uwlogo}
+\logo{\pgfuseimage{uw-logo}}
+
+\setbeamerfont{title}{size=\Huge}
+\beamersetuncovermixins{\opaqueness<1>{25}}{\opaqueness<2->{15}}
+
+\begin{document}
+\title{Combinatorial \\ and Approximation Algorithms}
+\author{Eric Johnson}
+\date{\today}
+
+\begin{frame}
+\titlepage
+\end{frame}
+
+\section{Introduction}
+\begin{frame}
+\begin{Large}
+Goal:
+\begin{center}
+\begin{figure}
+\mbox{\includegraphics[width=60mm]{img/venn.png}}
+\end{figure}
+\end{center}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Large}
+\begin{itemize}
+\item Introduction
+\item LP-Duality
+\item Dual fitting and LP Rounding
+\item Primal-dual schema
+\item More Applications
+\end{itemize}
+\end{Large}
+\end{center}
+\end{frame}
+
+\subsection{Background}
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Optimization Problems
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Find the best'' solution \\
+from a set of \\
+feasible solutions \\
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+\begin{itemize}
+\item Maximum Matching
+\item Vertex Cover
+\item MAX-3SAT
+\item Set Cover
+\item TSP
+\end{itemize}
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Most \\
+optimization problems \\
+are \\
+{\bf NP}-hard \\
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Our only hope...
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\mbox{\includegraphics[width=90mm]{img/obi-wan.jpg}}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Approximation Algorithms* \\ \vspace{10mm}
+\end{Huge}
+\end{center}
+\begin{flushright}
+* PCP theorem [Arora, et al], hardness of approximations
+\end{flushright}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Approximation algorithm strategies include: \\
+\begin{itemize}
+\item Greedy and Combinatorial Algorithms
+\item Linear Programming (LP) Rounding
+\item Primal-dual Schema
+\item Semidefinite Programming (SDP) Rounding
+\item Metric Methods
+\item Spectral Methods
+\end{itemize}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Our focus:
+\begin{itemize}
+\item Greedy and Combinatorial Algorithms
+\item LP rounding
+\item Primal-dual schema
+\end{itemize}
+\end{Large}
+\end{frame}
+
+\subsection{Set Cover}
+\begin{frame}
+\begin{Large}
+The Set Cover Problem \\ \vspace{5mm}
+From a collection of subsets
+\begin{equation*}
+\mathcal{S} = \{S_1, S_2, ..., S_n\}
+\end{equation*}
+of universe $U = \{e_1, e_2, ..., e_m\}$, find a minimum {\em cover} of $U$.
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+We will be considering weighted Set Cover \\ \vspace{5mm}
+so that we have a cost'' function:
+\begin{equation*}
+c:\mathcal{S} \rightarrow \mathbb{Q}^+
+\end{equation*}
+and we minimize over the sum of costs of the \\
+sets chosen.\\
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{flushleft}
+In 1972 \\
+\end{flushleft}
+\begin{center}
+\begin{Huge}
+Set Cover \\
+was shown to be \\
+{\bf NP}-Complete. \\ \vspace{5mm}
+\end{Huge}
+\end{center}
+\begin{flushright}
+It has since played a key role in the development of approximation algorithm techniques.
+\end{flushright}
+\end{frame}
+
+\begin{frame}
+Consider the following example: \\
+\vspace{5mm}
+\begin{tikzpicture}[scale=0.5]
+\draw (0,0) ellipse (7 and 1.5);
+\draw[rotate = 90] (0,5.5) ellipse (2 and 1);
+\draw[rotate = 90] (0,2.5) ellipse (2 and 1);
+\draw[rotate = 90] (0,-4.5) ellipse (2 and 1);
+\shade[ball color=black] (-5.5,0) circle (0.1);
+\shade[ball color=black] (-2.5,0) circle (0.1);
+\shade[ball color=black] (4.5,0) circle (0.1);
+\draw (-5.5,0.5) node{$e_n$};
+\draw (-2.5,0.5) node{$e_{n-1}$};
+\draw (4.5,0.5) node{$e_1$};
+\shade[ball color=black] (0.2,0) circle (0.03);
+\shade[ball color=black] (0.4,0) circle (0.03);
+\shade[ball color=black] (0.6,0) circle (0.03);
+\draw (-5.5,-3) node{$\dfrac{1}{n}$};
+\draw (-2.5,-3) node{$\dfrac{1}{n-1}$};
+\draw (4.5,-3) node{1};
+\draw (8,0) node{$1+\epsilon$};
+\end{tikzpicture}
+\\
+\vspace{5mm}
+The greedy algorithm is within
+\begin{equation*}
+\dfrac{1}{n} + \dfrac{1}{n-1} + ... + 1 = H_n
+\end{equation*}
+factor of optimal, OPT.
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+{\bf Theorem:} The greedy algorithm is an $H_n$ factor \\
+approximation algorithm for the minimum set \\
+cover problem where \\
+\begin{equation*}
+H_n = 1 + \dfrac{1}{2} + ... + \dfrac{1}{n-1} + \dfrac{1}{n}
+\end{equation*}
+\end{Large}
+\vspace{5mm}
+\begin{flushright}
+...and by PCP Theorem it's all we can hope for (unless {\bf P} = {\bf NP})
+\end{flushright}
+\end{frame}
+
+\section{LP-Duality}
+\subsection{Linear Programming Background and Examples}
+\begin{frame}
+\begin{Large}
+Linear Programming
+\begin{align*}
+\mbox{minimize} \hspace{4mm} & \sum_{j=0}^n c_j x_j \\
+\mbox{subject to} \hspace{4mm} & \sum_{j=0}^n a_{ij}x_j \geq b_i \\
+\mbox{and} \hspace{4mm} & x_j \geq 0
+\end{align*}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Example:
+\begin{center}
+\mbox{\includegraphics[width=80mm]{img/ex_2d_lp.jpg}}
+\end{center}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Why is \\
+Linear Programming \\
+useful to us? \\ \vspace{10mm}
+\end{Huge}
+\end{center}
+\begin{flushright}
+in approximation algorithm design
+\end{flushright}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Many \\
+optimization problems \\
+can be stated as \\
+integer programs \\
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+And since IP is \\
+a restricted'' LP, \\
+techniques from LP \\
+may elicit information
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Set Cover is an Integer Program:
+\begin{align*}
+\mbox{minimize} \hspace{4mm} & \sum_{S \in \mathcal{S}} c(S) x_S \\
+\mbox{subject to} \hspace{4mm} & \sum_{S: e \in S} x_S \geq 1, e \in U \\
+\mbox{and} \hspace{4mm} & x_S \in \{0, 1\}
+\end{align*}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Consider the following Set Cover problem. \\ \vspace{5mm}
+\end{Large}
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale=0.4]
+\draw (0,-1.8) ellipse (4 and 1.5);
+\draw[rotate = 60](0,1.8) ellipse (4 and 1.5);
+\draw[rotate = 120](0,-1.8) ellipse (4 and 1.5);
+\shade[ball color=black] (-3,-1.8) circle (0.1);
+\shade[ball color=black] (3,-1.8) circle (0.1);
+\shade[ball color=black] (0,3) circle (0.1);
+\draw (-2.5,-1.4) node{$e_1$};
+\draw (2.5,-1.4) node{$e_2$};
+\draw (0,3.5) node{$e_3$};
+\draw (0,-2) node{A};
+\draw (2,1) node{C};
+\draw (-2,1) node{B};
+\draw (0,-4) node{7};
+\draw (3.5,2.5) node{3};
+\draw (-3.5,2.5) node{5};
+\end{tikzpicture}
+\end{center}
+\end{figure}
+\begin{Large}
+We, therefore, have the following IP: \\
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{columns}[c]
+\column{.5\textwidth}
+\begin{alignat*}{4}
+\mbox{minimize} \hspace{4mm} & 7x_A & &+ 5x_B & &+ 3x_C & & \\
+ & \mbox{  }x_A & &+ \mbox{  }x_B & &               & & \geq 1 \\
+ & \mbox{  }x_A & &+              & &+ \mbox{  }x_C & & \geq 1 \\
+ & \mbox{  }    & &+ \mbox{  }x_B & &+ \mbox{  }x_C & & \geq 1 \\
+ & x_A & &, x_B & &, x_C & & \in \{0,1\}
+\end{alignat*}
+
+\column{.5\textwidth}
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale=0.4]
+\draw (0,-1.8) ellipse (4 and 1.5);
+\draw[rotate = 60](0,1.8) ellipse (4 and 1.5);
+\draw[rotate = 120](0,-1.8) ellipse (4 and 1.5);
+\shade[ball color=black] (-3,-1.8) circle (0.1);
+\shade[ball color=black] (3,-1.8) circle (0.1);
+\shade[ball color=black] (0,3) circle (0.1);
+\draw (-2.5,-1.4) node{$e_1$};
+\draw (2.5,-1.4) node{$e_2$};
+\draw (0,3.5) node{$e_3$};
+\draw (0,-2) node{A};
+\draw (2,1) node{C};
+\draw (-2,1) node{B};
+\draw (0,-4) node{7};
+\draw (3.5,2.5) node{3};
+\draw (-3.5,2.5) node{5};
+\end{tikzpicture}
+\end{center}
+\end{figure}
+\end{columns}
+\end{frame}
+
+\begin{frame}
+\begin{flushleft}
+An approach: \\
+\vspace{5mm}
+\end{flushleft}
+\begin{center}
+\begin{Huge}
+We can attempt to \\
+lower bound \\
+the objective function. \\
+\end{Huge}
+\end{center}
+\end{frame}
+
+\subsection{LP relaxations and the Dual Program}
+\begin{frame}
+We can consider the {\em LP-relaxation}: \\
+\begin{alignat*}{4}
+\mbox{minimize} \hspace{4mm} & 7x_A & &+ 5x_B & &+ 3x_C & & \\
+ & \mbox{  }x_A & &+ \mbox{  }x_B & &               & & \geq 1 \\
+ & \mbox{  }x_A & &+              & &+ \mbox{  }x_C & & \geq 1 \\
+ & \mbox{  }    & &+ \mbox{  }x_B & &+ \mbox{  }x_C & & \geq 1 \\
+ & x_A & &, x_B & &, x_C & & \geq 0
+\end{alignat*}
+It's trivial that $OPT_f \leq OPT$.
+\end{frame}
+
+\begin{frame}
+We can obtain immediate lower bounds to $OPT_f$ from each inequality \\
+\begin{figure}
+\mbox{\includegraphics[width=60mm]{img/dual_construction.png}}
+\end{figure}
+And, in fact, we can consider linear combinations of the these to provide better lower bounds. \\
+\end{frame}
+
+\begin{frame}
+The {\em dual program} provides us with a thorough'' approach to this lower bounding idea...
+\begin{columns}[c]
+\column{.5\textwidth}
+\begin{figure}
+\mbox{\includegraphics[width=60mm]{img/dual_construction.png}}
+\end{figure}
+
+\column{.5\textwidth}
+\begin{alignat*}{4}
+\mbox{maximize} \hspace{4mm} & y_{e_1} & &+ y_{e_2} & &+ y_{e_3} & & \\
+ & \mbox{  }y_{e_1} & &+ \mbox{  }y_{e_2} & &               & & \leq 7 \\
+ & \mbox{  }y_{e_1} & &+              & &+ \mbox{  }y_{e_3} & & \leq 5 \\
+ & \mbox{  }    & &+ \mbox{  }y_{e_2} & &+ \mbox{  }y_{e_3} & & \leq 3 \\
+ & y_{e_1} & &, y_{e_2} & &, y_{e_3} & & \geq 0
+\end{alignat*}
+\end{columns}
+\vspace{3mm}
+...by optimizing over arbitrary linear combinations of the inequalities.
+\end{frame}
+
+\begin{frame}
+\begin{columns}[c]
+\column{.5\textwidth}
+Primal Program:
+\begin{align*}
+\mbox{minimize} \hspace{4mm} & \sum_{j=0}^n c_j x_j \\
+\mbox{subject to} \hspace{4mm} & \sum_{j=0}^n a_{ij}x_j \geq b_i \\
+\mbox{and} \hspace{4mm} & x_j \geq 0
+\end{align*}
+
+\column{.5\textwidth}
+Dual Program:
+\begin{align*}
+\mbox{maximize} \hspace{4mm} & \sum_{i=1}^m b_i y_i \\
+\mbox{subject to} \hspace{4mm} & \sum_{i=0}^m a_{ij}y_i \leq c_j \\
+\mbox{and} \hspace{4mm} & y_i \geq 0
+\end{align*}
+\end{columns}
+\vspace{3mm}
+With some careful algebra, it can be shown that every dual feasible solution is less than or equal to every primal feasible solution.
+\end{frame}
+
+\subsection{LP-duality Theorem}
+\begin{frame}
+\begin{center}
+\begin{Huge}
+We can say more, \\
+however... \\
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+{\bf Theorem (LP-duality theorem):} \\
+\vspace{3mm}
+The primal program has finite optimum iff its dual has finite optimum. \\
+\vspace{3mm}
+Moreover, if $\mathbf{x}^* = (x_1^*, x_2^*, ... , x_n^*)$ and $\mathbf{y}^* = (y_1^*, y_2^*, ... , y_n^*)$ are optimal solutions for the primal and dual programs, respectively, then
+\begin{equation*}
+\sum_{j=1}^n c_j x_j^* = \sum_{i=1}^m b_i y_i^*
+\end{equation*}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+We can also speak \\
+to the structure of \\
+optimal solutions \\
+\end{Huge}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+{\bf Complementary Slackness Conditions} \\
+\vspace{3mm}
+Let $\mathbf{x}$ and $\mathbf{y}$ be primal and dual feasible solutions. Then, $\mathbf{x}$ and $\mathbf{y}$ are both optimal iff all of the following conditions are satisfied: \\
+\vspace{3mm}
+{\bf Primal complementary slackness conditions} \\
+For all $1 \leq j \leq n$: either $x_j = 0$ or $\sum_{i=1}^m a_{ij} y_i = c_j$; \\
+\vspace{3mm}
+{\bf Dual complementary slackness conditions} \\
+For all $1 \leq i \leq m$: either $y_i = 0$ or $\sum_{j=1}^m a_{ij} x_j = b_i$; \\
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Complementary \\
+Slackness Conditions \\
+\vspace{5mm}
+are vital \\
+to algorithm design \\
+\end{Huge}
+\end{center}
+\begin{flushright}
+we will return to this shortly...
+\end{flushright}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Huge}
+Two basic techniques for \\
+approximation algorithms \\
+using LP: \\
+\begin{itemize}
+\item LP-rounding
+\item Primal-dual schema
+\end{itemize}
+\end{Huge}
+\end{center}
+\end{frame}
+
+\section{LP Rounding}
+\begin{frame}
+\begin{Large}
+Dual fitting:
+\begin{enumerate}
+\item Start with a combinatorial algorithm
+\item Establish mapping with primal and dual programs
+\item Relax the LP
+\item Show the primal integral solution found is {\em fully paid for} by the dual computed
+\item Compute scaling factor and show shrunk dual is feasible
+\item This shrunk dual is lower bounds OPT
+\end{enumerate}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{columns}[c]
+\column{.5\textwidth}
+\begin{alignat*}{4}
+\mbox{minimize} \hspace{4mm} & 7x_A & &+ 5x_B & &+ 3x_C & & \\
+ & \mbox{  }x_A & &+ \mbox{  }x_B & &               & & \geq 1 \\
+ & \mbox{  }x_A & &+              & &+ \mbox{  }x_C & & \geq 1 \\
+ & \mbox{  }    & &+ \mbox{  }x_B & &+ \mbox{  }x_C & & \geq 1 \\
+ & x_A & &, x_B & &, x_C & & \in \{0,1\}
+\end{alignat*}
+
+\column{.5\textwidth}
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale=0.4]
+\draw (0,-1.8) ellipse (4 and 1.5);
+\draw[rotate = 60](0,1.8) ellipse (4 and 1.5);
+\draw[rotate = 120](0,-1.8) ellipse (4 and 1.5);
+\shade[ball color=black] (-3,-1.8) circle (0.1);
+\shade[ball color=black] (3,-1.8) circle (0.1);
+\shade[ball color=black] (0,3) circle (0.1);
+\draw (-2.5,-1.4) node{$e_1$};
+\draw (2.5,-1.4) node{$e_2$};
+\draw (0,3.5) node{$e_3$};
+\draw (0,-2) node{A};
+\draw (2,1) node{C};
+\draw (-2,1) node{B};
+\draw (0,-4) node{7};
+\draw (3.5,2.5) node{3};
+\draw (-3.5,2.5) node{5};
+\end{tikzpicture}
+\end{center}
+\end{figure}
+\end{columns}
+\end{frame}
+
+\begin{frame}
+\begin{center}
+\begin{Large}
+Result: \\
+\vspace{5mm}
+The method of dual fitting \\
+also provides an \\
+approximation guarantee of $H_n$ \\
+for the greedy set cover algorithm \\
+\end{Large}
+\end{center}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Set Cover and an LP-rounding algorithm:
+\begin{enumerate}
+\item Find an optimal solution to the LP-relaxation
+\item Pick all sets $S$ for which $x_S \geq \dfrac{1}{f}$ in this solution (where $f$ is the frequency of the most frequent element.)
+\end{enumerate}
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+{\bf Theorem:} This rounding algorithm is a factor $f$ approximation algorithm for the Set Cover problem.
+\end{Large}
+\begin{flushright}
+Actually, you can round all positively selected sets up to 1 and the factor still holds.
+\end{flushright}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+{\bf Theorem:} For the LP-relaxation for vertex cover:
+\begin{align*}
+\mbox{minimize} \hspace{4mm} & \sum_{v \in V} c(v) x_v \\
+\mbox{subject to} \hspace{4mm} & x_u + x_v \geq 1 (u,v) \in E \\
+\mbox{and} \hspace{4mm} & x_v \geq 0 v \in V
+\end{align*}
+any extreme point solution is half-integral.
+\end{Large}
+\begin{flushright}
+the argument uses properties of convex polyhedra and a simple partitioning
+\end{flushright}
+\end{frame}
+
+\begin{frame}
+Consider our problem:
+\begin{figure}
+\begin{center}
+\begin{tikzpicture}[scale=0.5]
+\draw (0,-1.8) ellipse (4 and 1.5);
+\draw[rotate = 60](0,1.8) ellipse (4 and 1.5);
+\draw[rotate = 120](0,-1.8) ellipse (4 and 1.5);
+\shade[ball color=black] (-3,-1.8) circle (0.1);
+\shade[ball color=black] (3,-1.8) circle (0.1);
+\shade[ball color=black] (0,3) circle (0.1);
+\draw (-2.5,-1.4) node{$e_1$};
+\draw (2.5,-1.4) node{$e_2$};
+\draw (0,3.5) node{$e_3$};
+\draw (0,-2) node{A};
+\draw (2,1) node{C};
+\draw (-2,1) node{B};
+\draw (0,-4) node{7};
+\draw (3.5,2.5) node{3};
+\draw (-3.5,2.5) node{5};
+\end{tikzpicture}
+\end{center}
+\end{figure}
+\end{frame}
+
+\section{Primal Dual Schema}
+\begin{frame}
+{\bf Relaxed Complementary Slackness Conditions}.\\
+\vspace{3mm}
+{\bf Primal complementary slackness conditions} \\
+Let $\alpha \geq 1$ \\
+For all $1 \leq j \leq n$: either $x_j = 0$ or $\dfrac{c_j}{\alpha} \leq \sum_{i=1}^m a_{ij} y_i \leq c_j$; \\
+\vspace{3mm}
+{\bf Dual complementary slackness conditions} \\
+Let $\beta \geq 1$ \\
+For all $1 \leq i \leq m$: either $y_i = 0$ or $b_i \leq \sum_{j=1}^m a_{ij} x_j \leq \beta \cdot b_i$; \\
+\end{frame}
+
+\begin{frame}
+{\bf Theorem:} If $\mathbf{x}$ and $\mathbf{y}$ are primal and dual feasible solutions satisfying the relaxed complementary slackness conditions then \\
+\begin{equation*}
+\sum_{j=1}^n c_j x_j \leq \alpha \cdot \beta \cdot \sum_{i=1}^m b_i y_i
+\end{equation*}
+\end{frame}
+
+\begin{frame}
+General methodology:
+\begin{enumerate}
+\item Start with initial feasible solutions
+\item Iteratively satisfy complementary slackness conditions
+\item If the primal conditions are met, set $\alpha = 1$. If the dual conditions are met, set $\beta = 1$.
+\item If both are satisfied, both solutions are optimal
+\end{enumerate}
+\end{frame}
+
+\section{More Applications}
+\begin{frame}
+\begin{center}
+\begin{Huge}
+We conclude with results \\
+of applying \\
+LP-rounding and metric methods \\
+to Demanded Multicommodity Flow \\
+\end{Huge}
+\end{center}
+\end{frame}
+
+\subsection{Sparsest Cut}
+\begin{frame}
+Consider an Orkut graph of friends \\
+\begin{figure}
+\mbox{\includegraphics[width=80mm]{img/orkut.png}}
+\end{figure}
+or any graph that can be overlaid with demands''
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Sparsest Cut problem \\
+\vspace{5mm}
+Let $G = (V, E)$ be a weighted graph \\
+with weights $\{c_e \in \mathbb{R}^+ \mid e \in E\}$  \\
+\vspace{5mm}
+Define demand pairs of vertices \\
+$\{(s_1, t_1), (s_2, t_2), \cdots , (s_k, t_k)\} \subseteq V \times V$ not necessarily edges \\
+together with an associated demand value $d_i$ \\
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Define the cost of a cut $E' \subseteq E$ as \\
+
+c(E') = \sum_{e \in E'} c_e
+
+and the demand as \\
+
+dem(E') = \sum_{s_i \mbox{ separated from } t_i \mbox{ by } E'} d_i
+
+where $s_i$ is separated from $t_i$ if the partition of $V$ by cut $E'$ leaves $s_i$ and $t_i$ in
+different components of the graph $G' = (V, E - E')$. \\
+\end{Large}
+\end{frame}
+
+\begin{frame}
+\begin{Large}
+Define the {\em sparsity} of a cut $E' \subseteq E$ to be \\
+\begin{equation*}
+\Phi(E') = \dfrac{c(E')}{dem(E')}
+\end{equation*}
+The Sparsest Cut problem then is one of finding a cut $E^* \subseteq E$ which minimizes $\Phi$. We
+define $\Phi^* = \min_{E' \subseteq E} \Phi(E')$. \\
+\end{Large}
+\end{frame}
+
+\begin{frame}
+Through the use of the dual LP, an $\mathcal{l}_1$ embedding into $O(log^2 k)$-dimensional space with low distortion, and an approximate cut packing, we can obtain $O(log k)$ approximation algorithm.
+\end{frame}
+
+\end{document}
+

# File prj/acmtrans2m.cls

+% latex2e by nr 7/3/96
+% acmtrans.cls revised 4/19/96
+%              revised again 31-JAN-1996 (see end of file)
+%              revised 5-14-1997 :
+%                       Don't use sans-serif font in categories and descriptors
+%                       include latexsym by default
+%                       Define longpage and shortpage
+% Adjusted from the acmtrans2e.cls file to the needs of ACM TOCL by
+% Marco Aiello on June 14, 2000.
+% Further changes made by Frederic Goualard on Sep. 27, 2000
+% to take care of the indentation problem in the bibliography
+% arising without the use of the hyperref package.
+% Modularization to adapt to the needs of JACM, TOCL,
+% TODAES, TODS, TOGS, TOMS, AND TOPLAS, by Marco Aiello on
+% June 2001.
+% Here is the basic framework that is needed to convert your paper
+% into ACM Transactions format and bibliographic format.  For a tutorial
+% introduction, see instructions.tex'' (compile it with LaTeX) that
+% accompanies the distribution of this style file.
+%
+%  -> \documentclass{acmtrans2m}
+%  -> \markboth{}{}
+%         takes 2 arguments and it is for the left- and right-page headers:
+%         the first set of braces is assigned for author's name(s)
+%         and
+%         the second set of braces is assigned for the title
+%             (if the title is too long, contraction may be needed
+%  -> \title{}
+%         if the title is too long, it can be separated by \\
+%  -> \author{}
+%         author1 \\ author1 affiliation
+%         \and
+%         author2 \\ author2 affiliation
+%  -> \begin{abstract}
+%  -> \end{abstract}
+%
+%  -> \category{}{}{}
+%         takes 3 arguments for the Computing Reviews Classification Scheme.
+%         ex: \category{D.3.3}{Programming Languages}{Language Constructs and
+%                   Features}[data types and structures]
+%                   the last argument, in square brackets, is optional.
+%  -> \terms{} (ex: \terms{Human Factors, Languages})
+%  -> \keywords{} (in alphabetical order \keywords{document processing, sequences,
+%                      string searching, subsequences, substrings})
+%  -> \begin{document}
+%
+%  -> \begin{bottomstuff}
+%          similar to \thanks
+%          for authors' addresses; research/grant statements
+%  -> \end{bottomstuff}
+%  -> \maketitle
+%
+%     Now you can start the body of the paper; your figures, tables and
+%          use all the latex constructs.
+%
+%  -> \begin{acks}
+%          acknowledgements
+%  -> \end{acks}
+%
+%  -> \bibliographystyle{acmtrans}
+%  -> \bibliography{mybib_file}
+%
+%     ****
+%     If your paper has been accepted with a separate (electronic only)
+%        appendix, you need to add the following control sequence:
+%
+%
+%       body of appendix
+%!!!!!! \appendixhead has be cut into two: \appendixhead and \elecappendix
+%!!!!!! See end of file. (jtb)
+%
+%  -> \end{document}
+%
+% Do not worry about the other definitions in this style file
+% Remember to compile: latex, bibtex, latex latex
+%
+% Bibliographic cite forms needed:
+%
+%  \cite{key}
+%    which produces citations with author list and year.
+%    eg. [Brown 1978; Jarke, et al. 1985]
+%  \citeA{key}
+%    which produces citations with only the author list.
+%    eg. [Brown; Jarke, et al.]
+%  \citeN{key}
+%    which produces citations with the author list and year, but
+%    can be used as nouns in a sentence; no brackets appear around
+%    the author names, but only around the year.
+%      eg. Shneiderman [1978] states that......
+%    \citeN should only be used for a single citation.
+%    \citeNN{refkey1,refkey2} for author [ref1year; ref2year]
+%    \citeyear{key}
+%        which produces the year information only, within brackets.
+%
+% Abbreviated author lists use the et al.'' construct.
+%
+% The above are examples of required ACM bibliographic cite formats needed.
+% *******************
+% Here is the complete list of cite forms from the chicago bibliographic style
+%
+%  \cite{key}
+%    which produces citations with abbreviated author list and year.
+%  \citeNP{key}
+%    which produces citations with abbreviated author list and year.
+%  \citeA{key}
+%    which produces only the abbreviated author list.
+%  \citeANP{key}
+%    which produces only the abbreviated author list.
+%  \citeN{key}
+%    which produces the abbreviated author list and year, with only the
+%    year in parentheses. Use with only one citation.
+%  \citeyear{key}
+%    which produces the year information only, within parentheses.
+%  \citeyearNP{key}
+%    which produces the year information only.
+%
+% Abbreviated author lists use the et al.'' construct.
+%
+% NP' means no parentheses'
+%
+
+\NeedsTeXFormat{LaTeX2e}
+\ProvidesClass{acmtrans2m} [1996/07/03 ACM Transactions class based on <23 April 96>]
+\RequirePackage{latexsym}
+%aiellom{
+\RequirePackage{url}
+
+% Do not change the following! Use the appropriate acmtocl, acmtods, ... option
+\def\@acmVolume{V} %the volume
+\def\@acmNumber{N} %the number
+\def\@acmYear{YY}  %the last two digits of the year,
+\def\@acmMonth{Month}  %the month
+\def\@journalName{ACM Journal Name} %the name of the ACM journal
+\def\@journalNameShort{jn} %the acronym of the ACM journal
+\def\@permissionCodeOne{0000-0000} %the permission code of the ACM journal
+\def\@permissionCodeTwo{0000} %the permission code of the ACM journal part 2
+\def\@pageCode{\acmPageCode} %the first page of the article in 4 digits
+
+
+\newif\if@acmjacm
+\newif\if@acmtocl
+\newif\if@acmtodaes
+\newif\if@acmtods
+\newif\if@acmtogs
+\newif\if@acmtoms
+\newif\if@acmtoplas
+
+\DeclareOption{acmnow}{
+  \typeout{}
+  \typeout{Directly generating the Month and Year for footers from the clock.}
+  \def\@acmYear{\yearTwoDigits}
+  \def\@acmMonth{\monthWord}
+}
+
+\DeclareOption{acmjacm}{
+  \typeout{}
+  \typeout{Using ACM, JACM's option: 2001/06/01 by Marco Aiello et al.}
+  \typeout{}
+  %\global\@acmjacmfalse
+  \global\@acmtoclfalse
+  \global\@acmtodaesfalse
+  \global\@acmtodsfalse
+  \global\@acmtogsfalse
+  \global\@acmtomsfalse
+  \global\@acmtoplasfalse
+  \global\@acmjacmtrue
+  \def\@journalName{Journal of the ACM}
+  \def\@journalNameShort{jacm}
+  \def\@permissionCodeOne{0004-5411}
+  \def\@permissionCodeTwo{0100}
+}
+
+\DeclareOption{acmtocl}{
+  \typeout{}
+  \typeout{Using ACM, TOCL's option: 2001/06/01 by Marco Aiello et al.}
+  \typeout{}
+  \global\@acmjacmfalse
+  \global\@acmtoclfalse
+  \global\@acmtodaesfalse
+  \global\@acmtodsfalse
+  \global\@acmtogsfalse
+  \global\@acmtomsfalse
+  \global\@acmtoplasfalse
+  \global\@acmtocltrue
+  \def\@journalName{ACM Transactions on Computational Logic}
+  \def\@journalNameShort{tocl}
+  \def\@permissionCodeOne{1529-3785}
+  \def\@permissionCodeTwo{0700}
+}
+
+\DeclareOption{acmtodaes}{
+  \typeout{}
+  \typeout{Using ACM, TODAES option: 2001/06/01 by Marco Aiello et al.}
+  \typeout{}
+  \global\@acmjacmfalse
+  \global\@acmtoclfalse
+  %\global\@acmtodaesfalse
+  \global\@acmtodsfalse
+  \global\@acmtogsfalse
+  \global\@acmtomsfalse
+  \global\@acmtoplasfalse
+  \global\@acmtodaestrue
+  \def\@journalName{ACM Transactions on Design Automation of Electronic Systems}
+  \def\@journalNameShort{todaes}
+  \def\@permissionCodeOne{1084-4309}
+  \def\@permissionCodeTwo{0400}
+}
+
+\DeclareOption{acmtods}{
+  \typeout{}
+  \typeout{Using ACM, TODS's option: 2001/06/01 by Marco Aiello et al.}
+  \typeout{}
+  \global\@acmjacmfalse
+  \global\@acmtoclfalse
+  \global\@acmtodaesfalse
+  %\global\@acmtodsfalse
+  \global\@acmtogsfalse
+  \global\@acmtomsfalse
+  \global\@acmtoplasfalse
+  \global\@acmtodstrue
+  \def\@journalName{ACM Transactions on Database Systems}
+  \def\@journalNameShort{tods}
+  \def\@permissionCodeOne{0362-5915}
+  \def\@permissionCodeTwo{0300}
+}
+
+\DeclareOption{acmtogs}{
+  \typeout{}
+  \typeout{Using ACM, TOGS's option: 2001/06/01 by Marco Aiello et al.}
+  \typeout{}
+  \global\@acmjacmfalse
+  \global\@acmtoclfalse
+  \global\@acmtodaesfalse
+  \global\@acmtodsfalse
+  %\global\@acmtogsfalse
+  \global\@acmtomsfalse
+  \global\@acmtoplasfalse
+  \global\@acmtogstrue
+  \def\@journalName{ACM Transactions on Graphics}
+  \def\@journalNameShort{togs}
+  \def\@permissionCodeOne{0730-0301}
+  \def\@permissionCodeTwo{0100}
+}
+
+\DeclareOption{acmtoms}{
+  \typeout{}
+  \typeout{Using ACM, TOMS's option: 2001/06/01 by Marco Aiello et al.}
+  \typeout{}
+  \global\@acmjacmfalse
+  \global\@acmtoclfalse
+  \global\@acmtodaesfalse
+  \global\@acmtodsfalse
+  \global\@acmtogsfalse
+  %\global\@acmtomsfalse
+  \global\@acmtoplasfalse
+  \global\@acmtomstrue
+  \def\@journalName{ACM Transactions on Mathematical Software}
+  \def\@journalNameShort{toms}
+  \def\@permissionCodeOne{0098-3500}
+  \def\@permissionCodeTwo{1200}
+}
+
+\DeclareOption{acmtoplas}{
+  \typeout{}
+  \typeout{Using ACM, TOPLAS option: 2001/06/01 by Marco Aiello et al.}
+  \typeout{}
+  \global\@acmjacmfalse
+  \global\@acmtoclfalse
+  \global\@acmtodaesfalse
+  \global\@acmtodsfalse
+  \global\@acmtogsfalse
+  \global\@acmtomsfalse
+  %\global\@acmtoplasfalse
+  \global\@acmtoplastrue
+  \def\@journalName{ACM Transactions on Programming Languages and Systems}
+  \def\@journalNameShort{toplas}
+  \def\@permissionCodeOne{0164-0925}
+  \def\@permissionCodeTwo{0500}
+}
+%}aiellom
+
+
+
+\if@compatibility\else
+\DeclareOption{a4paper}
+   {\setlength\paperheight {297mm}%
+    \setlength\paperwidth  {210mm}%
+    \def\special@paper{210mm,297mm}}
+\DeclareOption{a5paper}
+   {\setlength\paperheight {210mm}%
+    \setlength\paperwidth  {148mm}%
+    \def\special@paper{148mm,210mm}}
+\DeclareOption{b5paper}
+   {\setlength\paperheight {250mm}%
+    \setlength\paperwidth  {176mm}%
+    \setlength\voffset     {-15mm}%
+    \setlength\hoffset     {-20mm}%
+    \def\special@paper{176mm,250mm}}
+\DeclareOption{letterpaper}
+   {\setlength\paperheight {11in}%
+    \setlength\paperwidth  {8.5in}%
+    \def\special@paper{8.5in,11in}}
+\DeclareOption{legalpaper}
+   {\setlength\paperheight {14in}%
+    \setlength\paperwidth  {8.5in}%
+    \def\special@paper{8.5in,14in}}
+\DeclareOption{executivepaper}
+   {\setlength\paperheight {10.5in}%
+    \setlength\paperwidth  {7.25in}%
+    \def\special@paper{7.25in,10.5in}}
+\DeclareOption{landscape}
+   {\setlength\@tempdima   {\paperheight}%
+    \setlength\paperheight {\paperwidth}%
+    \setlength\paperwidth  {\@tempdima}}
+\fi
+
+\DeclareOption{checkMargin}{\setlength\overfullrule{5pt}}
+\DeclareOption{final}{\setlength\overfullrule{0pt}}
+
+\DeclareOption{oneside}{\@twosidefalse \@mparswitchfalse}
+\DeclareOption{twoside}{\@twosidetrue  \@mparswitchtrue}
+
+\DeclareOption{10pt}{\def\@ptsize{0}} %needed for amssymbols.sty
+\DeclareOption{11pt}{\ClassError{acmtrans}{11pt style not supported}
+                        {ACM transactions documents can be set in 10pt only}}
+\DeclareOption{12pt}{\ClassError{acmtrans}{11pt style not supported}
+                        {ACM transactions documents can be set in 10pt only}}
+\newif\if@hyperref
+\DeclareOption{hyperref}{%
+        \def\pages{\pageref{@firstpg}--\pageref{@lastpg}}%
+        \def\mypage{\thepage}%
+        \def\@getpagenum#1#2#3#4{#2}%
+        \def\pdfinfo#1#2{\pdfmark{pdfmark=/DOCINFO,Title=#1,Author=#2}}
+        \global\@hyperreftrue
+        }
+\DeclareOption{nohyperref}{
+                \def\pages{\pageref{@firstpg}--\pageref{@lastpg}}%
+                \def\@getpagenum#1#2{#2}%
+                \def\mypage{\thepage}%
+                \def\pdfinfo#1#2{}%
+                \def\pdfbookmark#1#2{}%
+                \global\@hyperreffalse
+                }
+\DeclareOption{notfinal}{
+                \def\pages{BD}%
+                \def\mypage{TBD}%
+                \def\@getpagenum#1#2{#2}%
+                \def\pdfinfo#1#2{}%
+                \def\pdfbookmark#1#2{}%
+                }
+\DeclareOption{omitline}{\def\@abstractbottom{\relax}}
+\DeclareOption{dontomitline}{\def\@abstractbottom{\if@acmjacm\else\hbox{\vrule height .2pt width 30pc}\fi}}
+\ExecuteOptions{twoside,notfinal,10pt,dontomitline,nohyperref,letterpaper} % defaults
+
+
+
+\ProcessOptions
+
+%{aiellom to automatize the issue specific data
+\def\acmVolume#1{\def\@acmVolume{#1}}
+\def\acmNumber#1{\def\@acmNumber{#1}}
+\def\acmYear#1{\def\@acmYear{#1}}
+\def\acmMonth#1{\def\@acmMonth{#1}}
+
+
+% Command to get the year from the system and display the last two digits
+\newcommand{\ignoretwo}[2]{}
+\newcommand{\yearTwoDigits}{\expandafter\ignoretwo\the\year}
+%To transform the month number in its name in English
+\newcommand{\monthWord}{\ifnum\the\month=1 January\fi\ifnum\the\month=2 February\fi\ifnum\the\month=3 March\fi\ifnum\the\month=4 April\fi\ifnum\the\month=5 May\fi\ifnum\the\month=6 June\fi\ifnum\the\month=7 July\fi\ifnum\the\month=8 August\fi\ifnum\the\month=9 September\fi\ifnum\the\month=10 October\fi\ifnum\the\month=11 November\fi\ifnum\the\month=12 December\fi}
+% overright the \@setref definition, so that if a reference is undefined
+% then it returns a number 0 and then the usual double boldface
+% question marks ??
+% this is necessary for the \acmPageCode command, otherwise it gives an error
+% everytime the aux file is not there
+\def\@setref#1#2#3{%
+  \ifx#1\relax
+    \number 0\relax
+    \protect\G@refundefinedtrue
+    \nfss@text{\reset@font\bfseries ??}%
+    \@latex@warning{Reference #3' on page \thepage \space undefined}%
+  \else
+    \expandafter#2#1\null
+  \fi}
+%make the code a four digits string based on the first page number
+\newcommand{\acmPageCode}{\bgroup
+  \newcount\c@tempo
+  \setcounter{tempo}{\number\pageref{@firstpg}}\ifnum \c@tempo<1000 0\fi\ifnum \c@tempo<100 0\fi\ifnum \c@tempo<10 0\fi\ifnum \c@tempo<1 0\fi\pageref{@firstpg}
+  \egroup
+}
+%}aiellom
+
+
+
+\lineskip 1pt \normallineskip 1pt
+\def\baselinestretch{1}
+
+\renewcommand\normalsize{%
+  \@setfontsize\normalsize\@xpt\@xiipt
+  \abovedisplayskip 6pt plus2pt minus1pt\belowdisplayskip \abovedisplayskip
+  \abovedisplayshortskip 6pt plus0pt minus 3pt
+  \belowdisplayshortskip 6pt plus0pt minus3pt\let\@listi\@listI} 
+
+\newcommand\small{%
+  \@setfontsize\small\@ixpt{11pt}%
+  \abovedisplayskip 5pt plus 2pt minus 1pt\belowdisplayskip \abovedisplayskip
+  \abovedisplayshortskip 5pt plus0pt minus2pt\belowdisplayshortskip 5pt plus0pt
+      minus 2pt
+  \def\@listi{\leftmargin\leftmargini \topsep 5pt plus 2pt minus 1pt\parsep 0pt
+    plus .7pt 
+  \itemsep 1.6pt plus .8pt}}
+\newcommand\footnotesize{%
+%   \@setfontsize\footnotesize\@viiipt{10pt}
+ \@setsize\footnotesize{10pt}\viiipt\@viiipt
+  \abovedisplayskip 4pt plus 1pt minus 0pt\belowdisplayskip \abovedisplayskip
+  \abovedisplayshortskip 4pt plus 0pt minus 1pt\belowdisplayshortskip 4pt plus
+       0pt minus 1pt
+  \def\@listi{\leftmargin\leftmargini \topsep 4pt plus 1pt minus
+     0pt\parsep 0pt plus .5pt 
+     \itemsep 1pt plus .7pt}}
+
+\newcommand\scriptsize{\@setfontsize\scriptsize\@viipt\@viiipt}
+\newcommand\tiny{\@setfontsize\tiny\@vpt\@vipt}
+\newcommand\large{\@setfontsize\large\@xiipt{14}}
+\newcommand\Large{\@setfontsize\Large\@xivpt{18}}
+\newcommand\LARGE{\@setfontsize\LARGE\@xviipt{20}}
+\newcommand\huge{\@setfontsize\huge\@xxpt{25}}
+\newcommand\Huge{\@setfontsize\Huge\@xxvpt{30}}
+
+\normalsize 
+
+ \oddsidemargin .75in \evensidemargin .75in \marginparwidth .5in 
+ \marginparsep .125in 
+ \topmargin .25in \headheight 12pt\headsep 16pt
+  %% not in latex2e  \footheight 10pt
+  \footskip 15pt 
+
+\textheight 47pc \textwidth 30pc \columnsep 10pt \columnseprule 0pt 
+% next five lines added by K.R. Apt, March 20, 01
+\advance\textheight-2.6pt
+\newdimen\normaltextheight
+\setlength\normaltextheight{\textheight}
+%\renewcommand\rmdefault{pnc}
+%\renewcommand\sfdefault{phv}
+
+
+\footnotesep 7pt
+\skip\footins 15pt plus 4pt minus 3pt 
+\floatsep 12pt plus 2pt minus 2pt 
+\textfloatsep \floatsep 
+\intextsep 1pc plus 1pc 
+%%% not in 2e %% \@maxsep 1pc 
+%%% not in 2e %% \@dblmaxsep 20pt 
+\dblfloatsep 12pt plus 2pt minus 2pt 
+\dbltextfloatsep 20pt plus 2pt minus 4pt 
+\@fptop 0pt plus 1fil \@fpsep 1pc plus 2fil \@fpbot 0pt plus 1fil 
+\@dblfptop 0pt plus 1fil \@dblfpsep 8pt plus 2fil \@dblfpbot 0pt plus 1fil
+\marginparpush 6pt 
+
+\parskip 0pt plus .1pt \parindent 10pt \partopsep 0pt 
+\@lowpenalty 51 \@medpenalty 151 \@highpenalty 301 
+\@beginparpenalty -\@lowpenalty \@endparpenalty -\@lowpenalty \@itempenalty
+-\@lowpenalty 
+
+
+\def\part{\@ucheadtrue
+ \@startsection{part}{9}{\z@}{-10pt plus -4pt minus 
+ -2pt}{4pt}{\reset@font\normalsize\sffamily}}
+\def\section{\@ucheadtrue
+ \@startsection{section}{1}{\z@}{-10pt plus -4pt minus 
+ -2pt}{4pt}{\reset@font\normalsize\sffamily}}
+\def\subsection{\@ucheadfalse
+ \@startsection{subsection}{2}{\z@}{-8pt plus -2pt minus 
+ -1pt}{4pt}{\reset@font\normalsize\sffamily}}
+\def\subsubsection{\@ucheadfalse
+ \@startsection{subsubsection}{3}{\parindent}{6pt plus 
+1pt}{-5pt}{\reset@font\normalsize\itshape}}
+\def\paragraph{\@ucheadfalse
+ \@startsection{paragraph}{3}{\parindent}{6pt plus 
+1pt}{-5pt}{\reset@font\normalsize\itshape}}
+
+\renewcommand{\@seccntformat}[1]{\textup{\csname the#1\endcsname}}
+
+\gdef\@period{.}
+\def\@trivlist{\@topsepadd\topsep
+\if@noskipsec \gdef\@period{}\leavevmode\gdef\@period{.}\fi
+ \ifvmode \advance\@topsepadd\partopsep \else \unskip\par\fi
+ \if@inlabel \@noparitemtrue \@noparlisttrue 
+ \else \@noparlistfalse \@topsep\@topsepadd \fi
+ \advance\@topsep \parskip
+ \leftskip\z@\rightskip\@rightskip \parfillskip\@flushglue
+ \@setpar{\if@newlist\else{\@@par}\fi} \global\@newlisttrue
+\@outerparskip\parskip}
+
+
+\def\@startsection#1#2#3#4#5#6{%
+  \if@noskipsec \leavevmode \fi
+  \par
+  \@tempskipa #4\relax
+  \@afterindenttrue
+  \ifdim \@tempskipa <\z@
+    \@tempskipa -\@tempskipa \@afterindentfalse
+  \fi
+  \if@nobreak
+    \everypar{}%
+  \else
+    \addpenalty\@secpenalty\addvspace\@tempskipa
+  \fi
+  \@ifstar
+    {\@ssect{#3}{#4}{#5}{#6}}%
+    {\@dblarg{\@sect{#1}{#2}{#3}{#4}{#5}{#6}}}}
+\def\@sect#1#2#3#4#5#6[#7]#8{%
+  \ifnum #2>\c@secnumdepth
+    \let\@svsec\@empty
+  \else
+    \refstepcounter{#1}%
+      \if@uchead%
+            \protected@edef\@svsec{\@seccntformat{#1}.\quad\relax}%
+        \else%
+            \protected@edef\@svsec{\@seccntformat{#1}\quad\relax}%
+        \fi%
+  \fi
+  \@tempskipa #5\relax
+  \ifdim \@tempskipa>\z@
+    \begingroup
+      #6{%
+        \@hangfrom{\hskip #3\relax\@svsec}%
+          \interlinepenalty \@M \if@uchead\MakeUppercase{#8}\else#8\fi \@@par}%
+    \endgroup
+    \csname #1mark\endcsname{#7}%
+    \addcontentsline{toc}{#1}{%
+      \ifnum #2>\c@secnumdepth \else
+        \protect\numberline{\csname the#1\endcsname}%
+      \fi
+      #7}%
+  \else
+    \def\@svsechd{%
+      #6{\hskip #3\relax
+      \@svsec \if@uchead\Makeuppercase{#8}\else#8\fi}%
+      \csname #1mark\endcsname{#7}%
+      \addcontentsline{toc}{#1}{%
+        \ifnum #2>\c@secnumdepth \else
+          \protect\numberline{\csname the#1\endcsname}%
+        \fi
+        #7}}%
+  \fi
+  \@xsect{#5}}
+
+\def\@xsect#1{\@tempskipa #1\relax
+ \ifdim \@tempskipa>\z@
+ \par \nobreak
+ \vskip \@tempskipa
+ \@afterheading
+ \else \global\@nobreakfalse \global\@noskipsectrue
+ \everypar{\if@noskipsec \global\@noskipsecfalse
+ \clubpenalty\@M \hskip -\parindent
+ \begingroup \@svsechd\@period \endgroup \unskip
+ \hskip -#1
+ \else \clubpenalty \@clubpenalty
+ \everypar{}\fi}\fi\ignorespaces}
+\newif\if@uchead\@ucheadfalse
+
+
+\setcounter{secnumdepth}{3}
+\newcounter{secnumbookdepth}
+\setcounter{secnumbookdepth}{3}
+
+\newfont{\apbf}{cmbx9}
+
+\def\@withappendix#1{App--\number #1}
+
+\newcommand{\elecappendix}{
+}
+
+\def\appenheader{\global\@topnum\z@ \global\@botroom \textheight \begin{figure}
+\newfont{\sc}{cmcsc10}
+\parindent\z@
+\hbox{}
+\vskip -\textfloatsep
+\vskip 11pt
+\hrule height .2pt width 30pc
+\vskip 2pt\rule{0pt}{10pt}\ignorespaces}
+\def\endappenheader{\end{figure}\gdef\appendixhead{}}
+
+\def\@appsec{}
+
+\def\appendix{\par
+ \setcounter{section}{0}
+ \setcounter{subsection}{0}
+ \def\@appsec{APPENDIX } 
+        \def\thesection{\Alph{section}}
+        \def\theHsection{\Alph{section}}}
+
+
+
+\labelsep 5pt
+\settowidth{\leftmargini}{(9)} \addtolength\leftmargini\labelsep
+\settowidth{\leftmarginii}{(b)} \addtolength\leftmarginii\labelsep
+\leftmarginiii \leftmarginii
+\leftmarginiv \leftmarginii 
+\leftmarginv \leftmarginii 
+\leftmarginvi \leftmarginii 
+\leftmargin\leftmargini
+\labelwidth\leftmargini\advance\labelwidth-\labelsep
+\def\@listI{\leftmargin\leftmargini \parsep 0pt plus 1pt\topsep 6pt plus 2pt
+minus 2pt\itemsep 2pt plus 1pt minus .5pt}
+\let\@listi\@listI
+\@listi 
+\def\@listii{\leftmargin\leftmarginii
+ \labelwidth\leftmarginii\advance\labelwidth-\labelsep
+ \topsep 0pt plus 1pt 
+ \parsep 0pt plus .5pt 
+ \itemsep \parsep}
+\def\@listiii{\leftmargin\leftmarginiii
+ \labelwidth\leftmarginiii\advance\labelwidth-\labelsep
+ \topsep 0pt plus 1pt 
+ \parsep 0pt plus .5pt 
+ \itemsep \parsep}
+\def\@listiv{\leftmargin\leftmarginiv
+ \labelwidth\leftmarginiv\advance\labelwidth-\labelsep}
+\def\@listv{\leftmargin\leftmarginv
+ \labelwidth\leftmarginv\advance\labelwidth-\labelsep}
+\def\@listvi{\leftmargin\leftmarginvi
+ \labelwidth\leftmarginvi\advance\labelwidth-\labelsep}
+
+
+
+
+\def\enumerate{\ifnum \@enumdepth >3 \@toodeep\else
+ \advance\@enumdepth \@ne 
+ \edef\@enumctr{enum\romannumeral\the\@enumdepth}\list
+ {\csname label\@enumctr\endcsname}{\usecounter
+ {\@enumctr}\def\makelabel##1{##1\hss}}\fi}
+\def\longenum{\ifnum \@enumdepth >3 \@toodeep\else
+ \advance\@enumdepth \@ne 
+ \edef\@enumctr{enum\romannumeral\the\@enumdepth}\list
+ {\csname label\@enumctr\endcsname}{\usecounter
+ {\@enumctr}\labelwidth\z@}\fi}
+%\leftmargin\z@ \itemindent\parindent}\fi} - this indents each item in enumerate
+\let\endlongenum\endlist
+%%--------------------CHANGED: always roman parentheses. dave ---------------%%
+\def\labelenumi{{\rm (}\arabic{enumi}\/{\rm )}} 
+\def\theenumi{\arabic{enumi}} 
+\def\labelenumii{{\rm (}\alph{enumii}\rm{)}}
+\def\theenumii{\alph{enumii}}
+\def\p@enumii{\theenumi}
+\def\labelenumiii{\roman{enumiii}.}
+\def\theenumiii{\roman{enumiii}}
+\def\p@enumiii{\theenumi{\rm (}\theenumii{\rm )}}
+\def\labelenumiv{\Alph{enumiv}.}
+\def\theenumiv{\Alph{enumiv}} 
+\def\p@enumiv{\p@enumiii\theenumiii}
+
+\def\p@enumiv{\p@enumiii\theenumiii}
+
+\def\itemize{\list{---\hskip -\labelsep}{\settowidth
+ {\leftmargin}{---}\labelwidth\leftmargin
+ \addtolength{\labelwidth}{-\labelsep}}}
+\let\enditemize\endlist
+\def\longitem{\list{---}{\labelwidth\z@
+ \leftmargin\z@ \itemindent\parindent \advance\itemindent\labelsep}}
+\let\endlongitem\endlist
+\def\verse{\let\\=\@centercr 
+ \list{}{\leftmargin 2pc 
+ \itemindent -1.5em\listparindent \itemindent 
+ \rightmargin\leftmargin\advance\leftmargin 1.5em}\item[]}
+\let\endverse\endlist
+\def\quotation{\list{}{\leftmargin 2pc \listparindent .5em
+ \itemindent\listparindent
+ \rightmargin\leftmargin \parsep 0pt plus 1pt}\item[]}
+\let\endquotation=\endlist
+\def\quote{\list{}{\leftmargin 2pc \rightmargin\leftmargin}\item[]}
+\let\endquote=\endlist
+
+\def\description{\list{}{\listparindent\parindent\labelwidth\z@
+ \leftmargin\z@ \itemindent\parindent\advance\itemindent\labelsep
+ \def\makelabel##1{\it ##1.}}}
+\let\enddescription\endlist
+
+\def\describe#1{\list{}{\listparindent\parindent\settowidth{\labelwidth}{#1}\leftmargin
+ \labelwidth\addtolength\leftmargin\labelsep\def\makelabel##1{##1\hfil}}}
+\let\enddescribe\endlist
+
+        \def\program{\ifx\@currsize\normalsize\small \else \rm \fi\tabbing}
+        \let\endprogram\endtabbing
+         \def\@begintheorem#1#2{\trivlist \item[\hskip 10pt\hskip 
+         \labelsep{\sc{#1}\hskip 5pt\relax #2.}] \itshape}
+        % aiellom{: this is what makes the theorem environment with names 
+        % ABOVE #1 is the word example, corollary, etc.
+        %            #2 is the number
+        % \def\@opargbegintheorem#1#2#3{\trivlist
+        % \item[\hskip 10pt \hskip \labelsep{\sc #1\savebox\@tempboxa{#3}\ifdim 
+        % \wd\@tempboxa>\z@ \hskip 5pt\relax \box\@tempboxa\fi.}] \itshape}
+        %  is been changed to
+        % #1 is the word theorem, lemma, etc.
+        % #2 is the number
+        % #3 is the name of the theorem, lemma, etc.
+        \def\@opargbegintheorem#1#2#3{\trivlist
+        \item[\hskip 10pt \hskip 
+\labelsep{\sc{#1}\savebox\@tempboxa{\sc{#3}}\ifdim `