\documentclass[11pt]{amsart}
\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage[usenames]{xcolor}
\usepackage{enumerate}
\usepackage[ruled,noline,noend]{algorithm2e}
\usepackage{fullpage}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\theoremstyle{plain}
\newcommand{\AC}{\mathrm{AC}}
\newcommand{\cost}{\mathrm{cost}}
\DeclareMathOperator{\E}{\mathrm{E}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\rank}{\mathrm{rank}}
\newcommand{\replacethistext}[1]{{\color{red} #1}}
\title{
CS 466/666: Algorithm Design and Analysis \\
Problem Set 6}
\author{Due on: November 29, 2017}
\begin{document}
\begin{flushright}
\textbf{
\replacethistext{Your name} \\
\replacethistext{Your student number}
}
\end{flushright}
\medskip
\maketitle
\section*{Acknowledgements.}
\replacethistext{Acknowledge {\bf all collaborators} with whom you discussed any of the problems in this problem set and {\bf all external sources} that you may have used in the completion of the assignment. See the website for the full homework policy.}
%%% PROBLEM 1 %%%
\section{Problem 1: Approximating \textsc{MaxCut}}
An algorithm $\mathcal{A}$ is an \emph{$\alpha$-approximation algorithm} for \textsc{MaxCut} for some $0 < \alpha \le 1$ if for every graph $G$ the algorithm returns a cut $\mathcal{A}(G)$ of size
\[
\frac{|\mathcal{A}(G)|}{|\mathrm{OPT}(G)|} \ge \alpha
\]
where $\mathrm{OPT}(G)$ is the maximum cut of $G$.
\begin{enumerate}[(i)]
\item Show that there is an efficient $\frac12$-approximation algorithm for \textsc{MaxCut}.
\begin{theorem}
There is a polynomial-time $\frac12$-approximation algorithm for \textsc{MaxCut}.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\medskip \noindent \emph{Hint.} You may want to design a greedy algorithm that considers the vertices one at a time in an arbitrary order. \bigskip
\item Let \textsc{DirectedMaxCut} be the variant of \textsc{MaxCut} where the goal is to find the partition $(S,V \setminus S)$ of the vertices of a directed graph $G = (V,E)$ that maximizes the number of directed edges going from $S$ to $E \setminus S$. Show that this problem can also be efficiently approximated.
\begin{theorem}
There is a polynomial-time $\frac14$-approximation algorithm for \textsc{DirectedMaxCut}.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item {\bf Bonus.} Can you improve either of these bounds?
\end{enumerate}
%%% PROBLEM 2 %%%
\newpage
\section{Problem 2: Travelling with few weights}
An special case of the Metric TSP problem is the \textsc{$(1,2)$-TSP} problem where each edge weight in the complete graph is either $1$ or $2$. You will show how to improve on the best-known approximation algorithm for Metric TSP in this case.
\begin{enumerate}[(i)]
\item A \emph{minimum double matching} in a weighted graph is a minimum-weight collection $M$ of edges such that each vertex is adjacent to exactly $2$ edges in $M$. Prove that there is an efficient algorithm for finding a minimum double matching. You may use results from previous courses (e.g., CS 341) without proof in your answer if you give precise statements and references.
\begin{lemma}
There is a polynomial-time algorithm for finding a minimum double matching in the complete weighted graph.
\end{lemma}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item Use the result above to obtain a competitive TSP tour.
\begin{theorem}
There is a polynomial-time $\frac43$-approximation algorithm for the \textsc{$(1,2)$-TSP} problem.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item {\bf Bonus.} Can you generalize the result to obtain approximation algorithm for the \textsc{$1$-to-$k$-TSP} problem where the weights in the graphs must be integers in the set $\{1,\ldots,k\}$ for some $k \ge 3$?
\end{enumerate}
%%% PROBLEM 3 %%%
\newpage
\section{Problem 3: Covering vertices}
There is a very natural algorithm for the \textsc{VertexCover} problem that at each step adds the vertex which covers the largest number of still-uncovered edges:
\begin{algorithm}
\caption{\textsc{VC2}$(V, E)$}
$S \gets \emptyset$\;
\While{$E \neq \emptyset$}{
Let $v \in V$ be the vertex that covers the largest number of edges in $E$\;
$S \gets S \cup \{v\}$\;
$E \gets E \setminus \{ (u,v) : u \in V\}$\;
}
Return $S$\;
\end{algorithm}
The goal of this question is to show that this algorithm is a $O(\log n)$-approximation algorithm for \textsc{VertexCover}.
\begin{enumerate}[(i)]
\item Define the \emph{cost} of an edge $e \in E$ by running the VC2 algorithm, determining the number $t_e$ of (previously-uncovered) edges covered by the vertex $v$ that covers $e$ in the algorithm, and setting $\cost(e) = 1/t_e$.
\begin{lemma}
The size of the vertex cover returned by VC2 satisfies
\[
|S| = \sum_{e \in E} \cost(e).
\]
\end{lemma}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item Let $e_1,\ldots,e_n$ be an ordering of the edges in $E$ according to the order in which they are covered in the algorithm VC2.
\begin{lemma}
For every $k \le n$, the cost of edge $e_k$ satisfies
\[
\cost(e_k) \le \frac{\mathrm{OPT}}{n-k+1}
\]
where $\mathrm{OPT}$ is the size of the optimal vertex cover of the graph.
\end{lemma}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item The harmonic numbers satisfy the bound $H_n := 1 + \frac12 + \frac13 + \cdots \frac1n = O(\log n)$. Use this fact and the results above to show that VC2 is a valid approximation algorithm for \textsc{VertexCover}.
\begin{theorem}
VC2 is a $O(\log n)$-approximation algorithm for \textsc{VertexCover}.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item {\bf Bonus.} Show that the bound in the theorem is tight for some graphs.
\end{enumerate}
%%% PROBLEM 4 %%%
\newpage
\section{Problem 4: Variant of disjointness}
Let $2^{[n]}$ denote the set of subsets of $[n] = \{1,2,\ldots,n\}$ and fix $k \ge 1$. The function $\textsc{Disjoint}_k : 2^{[n]} \times 2^{[n]} \to \{0,1\}$ is defined by
\[
\textsc{Disjoint}_k(S,T) =
\begin{cases}
1 & \mbox{if } S \cap T = \emptyset, |S| \le k \mbox{, and } |T| \le k \\
0 & \mbox{otherwise.}
\end{cases}
\]
Establish the following bounds on the communication complexity of the $\textsc{Disjoint}_k$ function.
\begin{enumerate}[(i)]
\item Show that when $k$ is small, the communication complexity of $\textsc{Disjoint}_k$ is also (fairly) small.
\begin{theorem}
For every $k \ge 1$, $D^{CC}(\textsc{Disjoint}_k) = O(k \log n)$.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item Show that, conversely, when $k$ is large, the communication complexity of $\textsc{Disjoint}_k$ is also (fairly) large.
\begin{theorem}
For every $k \ge 1$, $D^{CC}(\textsc{Disjoint}_k) \ge k$.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\item {\bf Bonus.} Show that the communication complexity of $\textsc{Disjoint}_k$ must depend on $n$.
\begin{theorem}
For every $k \ge 1$, $D^{CC}(\textsc{Disjoint}_k) \ge \log(\tfrac{n}{k})$.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
For an extra bonus challenge: close the gap between the upper and lower bounds on the communication complexity of $\textsc{Disjoint}_k$! (Warning: I suspect the true communication complexity is $\Theta(k \log n)$, but I don't have a proof of that fact at the moment---and if that bound is correct, it's possible that it is not achievable via the fooling set method.)
\end{enumerate}
%%% PROBLEM 5 %%%
\newpage
\section{Problem 5: Palindromes}
A \emph{simple Turing machine algorithm} is an algorithm that receives its input $x \in \{0,1\}^n$ on a tape and has only $O(1)$ bits of additional memory. Initially, the algorithm sees the first bit of the input. At each time step, an algorithm in this model can overwrite the current bit that it sees with an \texttt{X} or leave the current bit as is, then move one step to the left or to the right. The \emph{time complexity} of an algorithm in this model is the number of time steps that elapse before the algorithm terminates and outputs its answer.
The $\textsc{Palindrome} : \{0,1\}^n \to \{0,1\}$ function determines if its input $x = (x_1,\ldots,x_n)$ is identical to its reverse $x^R = (x_n,\ldots,x_1)$. Formally,
\[
\textsc{Palindrome}(x) = \begin{cases}
1 & \mbox{if } x = x^R \\
0 & \mbox{otherwise.}
\end{cases}
\]
It's not hard to see that there is a simple Turing machine algorithm that computes \textsc{Palindrome} in time $O(n^2)$. (How?)
\begin{enumerate}[(i)]
\item Show that the simple algorithm for \textsc{Palindrome} is optimal.
\begin{theorem}
Every simple Turing machine algorithm for \textsc{Palindrome} has time complexity $\Omega(n^2)$.
\end{theorem}
\begin{proof}
\replacethistext{Enter your answer here.}
\end{proof}
\medskip \noindent \emph{Hint.} You may want to consider inputs of the form $x\underbrace{000\cdots0}_{n}y^R$ for some $x,y \in \{0,1\}^n$.
\bigskip
\item
{\bf Bonus.} Show that the same $\Omega(n^2)$ bound holds even when we consider \emph{general} Turing machine algorithms, which can overwrite characters on the input tape with any bit (and not just overwrite them with \texttt{X}s).
\end{enumerate}
\end{document}