\documentclass[12pt]{article}

\usepackage{graphicx}
\usepackage{amsmath,amssymb,url}
\usepackage{bbm}

\newfont{\bssdoz}{cmssbx10 scaled 1200}
\newfont{\bssten}{cmssbx10}


\oddsidemargin  0in \evensidemargin 0in \topmargin -0.5in
\headheight 0.25in \headsep 0.25in
\textwidth   6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt
\parskip 1.5ex  \parindent 0ex \footskip 20pt

\begin{document}
\parindent 0ex
\thispagestyle{empty} \vspace*{-0.75in}
{\bssdoz CME 305: Discrete Mathematics and Algorithms}
{\\ \bssten Instructor: Professor Amin Saberi (saberi@stanford.edu) }
{\\ \bssten HW\#4 --  Due 3/16/12}
\vspace{5pt}

\begin{enumerate}

\item
Given a connected, undirected graph $G = (V,E)$ and a set of terminals
$S=\{s_1, s_2,\ldots,s_k\} \subseteq V$, a multiway cut is a set of edges whose 
removal disconnects the terminals from each other. The multiway cut problem asks for the minimum weight such set.
The problem of finding a minimum weight multiway cut is NP-hard for any fixed $k \geq 3$.
Observe that the case $k = 2$ is precisely the minimum $s-t$ cut problem.

Define an \textit{isolating cut} for $s_i$ to be a set of edges whose removal disconnects $s_i$ from the rest of the terminals. Consider the following algorithm
\begin{itemize}
	\item For each $i = 1,\ldots, k$, compute a minimum weight isolating cut for $s_i$, say $C_i$.
	\item Discard the heaviest of these cuts, and output the union of the rest, say C.
\end{itemize}

Each computation in Step 1 can be accomplished by identifying the $terminals$ in $S - \{s_i\}$ into a single node, and finding a minimum cut separating this node from $s_i$; this takes one max-flow computation. Clearly, removing $C$ from the graph disconnects every pair of terminals, and so is a multiway cut.

\begin{enumerate}
\item Prove that this algorithm achieves a $2-2/k$ approximation.
\item Prove that this analysis is tight by providing an example graph where the approximation bound is exactly achieved.
\end{enumerate}

\item Consider variants on the metric TSP problem in which the object is to find a simple path containing all the vertices of the graph. Three different problems arise, depending on the number (0, 1, or 2) of endpoints of the path that are specified. Obtain the following approximation algorithms.
\begin{enumerate}
\item  If zero or one endpoints are specified, obtain a 3/2 factor algorithm. 
\item If both endpoints are specified, obtain a 5/3 factor algorithm.
\end{enumerate}
\textbf{Hint.} Consider modifying Christofides algorithm for metric TSP.

\item Recall the \emph{minimum vertex cover} problem: given a graph
$G(V,E)$ find a subset $S^* \subseteq V$ with minimum cardinality such
that every edge in $E$ has at least one endpoint in $S^*$.
\begin{enumerate}
\item Consider the following greedy algorithm. Find the highest degree
vertex, add it to the vertex cover $S$ and remove it along with all
incident edges. Repeat iteratively. Prove that this algorithm has an
unbounded approximation factor i.e.  for any $c$ there exists an input
graph $G$ such that $|S|$ $\geq c$ OPT.

\item Prove that when the graph $G$ is bipartite we can find the minimum
vertex cover in polynomial time. State your algorithm.

\end{enumerate}

\item Consider scheduling $n$ jobs to $m$ identical machines to minimize the time taken by the machine
with the heaviest load (i.e. to minimize the makespan). One algorithm we saw in class
was to order the jobs by decreasing processing times $t_1 \geq t_2 \geq \ldots \geq t_n$, then greedily assign jobs
to the machine whose load is the smallest so far (starting with the heaviest job).
\begin{enumerate}
\item Show that this algorithm is a $4/3$ approximation to the optimal makespan.
\item Show that the $4/3$ approximation is tight for this algorithm.
\end{enumerate}

\item Give a $O(\log n)$ factor approximation to the \emph{Asymmetric
Travelling Salesman Problem}. ATSP: We are given a set of points $V$ and
a cost function $c \, : \, V \times V \to [0,\infty)$ which defines a
cost of travel from point $u$ to point $v$ as $c(u,v)$. Note, here we
have asymmetry i.e. in general $c(u,v) \neq c(v,u)$. Assume further that
the triangle inequality is satisfied i.e. $c(u,v) \leq c(u,w) + c(w,v)$
for all $u,v,w \in V$.  ATSP asks to find a minimum cost cycle which
visits each vertex exactly once.

{\bf Hint:} Use the fact that a minimum cost cycle cover (i.e. set of
disjoint cycles covering all the vertices) can be found in polynomial
time. Shrink the cycles and recurse.

\item {\bf (Kleinberg \& Tardos 13.1)} \emph{3-Coloring} is a yes/no
question, but we can phrase it as an optimization problem as follows.

Suppose we are given a graph $G(V,E)$, and we want to color each node
with one of three colors, even if we aren't necessarily able to give
different colors to every pair of adjacent node.  Rather, we say that
an edge $(u,v)$ is \emph{satisfied} if the colors assigned to $u$ and
$v$ are different.

Consider a 3-coloring that maximizes the number of satisfied edges,
and let $c^*$ denote this number.  Give a polynomial-time algorithm
that produces a 3-coloring that satisfies at least $\frac{2}{3}c^*$
edges.  If you want, your algorithm can be randomized; in this case,
the \emph{expected} number of edges it satisfies should be at least
$\frac{2}{3}c^*$.


\end{enumerate}

\end{document}