\documentclass[11pt]{article}
%\usepackage{pstricks,pst-node}
\usepackage{alltt,fullpage,graphics,color,epsfig,amsmath, amssymb, tikz, xfrac}
\usepackage{hyperref}
\usepackage{boxedminipage}
%\newcommand{\edgee}[1]{\begin{math}\stackrel{#1}{\longrightarrow}\end{math}}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}
\newcommand{\ceil}[1]{\lceil #1 \rceil}
\DeclareMathOperator*{\E}{\mathbb{E}}
\newcommand{\eps}{\epsilon}
\begin{document}
\setlength{\parskip}{.1 in}
\begin{center}
\LARGE
\textbf{CS 473: Algorithms, Spring 2018}
\\[0.5ex]
\textbf{HW 11 (due Wednesday, May 2$^\text{nd}$ at 8pm)}
\end{center}
\noindent
This homework contains three problems. {\bf Read the instructions for
submitting homework on the course webpage}.
\noindent {\bf Collaboration Policy:} For this home work, each student
can work in a group with up to three members. Only one solution for
each group needs to be submitted. Follow the submission instructions
carefully.
\hrule
\medskip\noindent
For problems that ask for approximation algorithm, a full credit solution requires the following components:
\begin{itemize}\itemsep0pt
\item An algorithm that runs in polynomial time and retuns a valid solution (although sub-optimal).
\item Proof of correctness and running time of the algorithm.
\item Proof of approximation factor of the algorithm. This typically involveÑ• lower bounding OPT, and then obtaining an upper bound on the {\em value of the solution returned by your algorithm} as a function of lower bounds of OPT.
\end{itemize}
\hrule
\bigskip
\bigskip
\begin{enumerate}
%----------------------------------------------------------------------
\item Provide a $\sfrac 12$-factor, polynomial time, approximation algorithm for the \textsc{Acyclic Subgraph}
problem:
\begin{center}
\parbox{0.9\textwidth}{
\textbf{Input.} An directed graph $G=(V,E)$.\\[1em]
\textbf{Output.} A maximum-cardinality set of edges $E'\subseteq E$ such that $G[E']$ is acyclic.
}
\end{center}
{\em \textbf{Hint.} Arbitrarily number the vertices from 1 to $n$. Let $E_+$ be the edges going in an increasing
direction, and $E_-$ be those in a decreasing direction. Pick the biggest of $E_+$ and $E_-$.}
\item Recall as discussed in class, that one possible 2-approximation for the \textsc{Vertex Cover}
problem involves solving the LP relaxation of the standard integer linear program, and rounding up to
1 every coordinate where the optimal value was at least $\sfrac 12$.
This question asks you to extend this technique to the \textsc{Set Cover} problem:
\begin{center}
\parbox{0.9\textwidth}{
\textbf{Input.} A ground set $U=\{1,\,2,\,\dotsc,\,m\}$, and a collection of $n$ subsets
$S_1,\,\dotsc,\,S_n\subseteq U$.\\[1em]
\textbf{Output.} The minimum collection of these subsets which ``covers'' $U$, namely,
a minimum-cardinality set $I\subseteq \{1,\,\dotsc,\,n\}$ such that $\bigcup_{i\in I} S_i=U$.
}
\end{center}
\begin{enumerate}
\item Get a factor $k$, polynomial time, approximation algorithm for \textsc{Set Cover}, where $k$ is the largest size of a subset, i.e., $k=\max_{i} |S_i|$.
\item Extend the \textsc{Vertex Cover} LP-rounding technique to get a factor $f$, polynomial time, approximation algorithm for \textsc{Set Cover}, where $f$ is the maximum number of times some element appears in the subsets.
(If $f_i:=|\{j:S_j\ni i\}|$, then $f=\max_i f_i$.)
\end{enumerate}
\item In the Max-SAT problem we are given a SAT formula $\varphi$ and
the goal is to find an assignment that satisfies the maximum number
of clauses. Consider an oblivious randomized algorithm that sets each
variable independently to TRUE with probability exactly $1/2$.
\begin{enumerate}
\item Suppose the formula is a $k$-SAT formula where each clause has
exactly $k$ distinct literals. What is the expected number of clauses
satisfied by a random assignment? Interestingly for $3$-SAT, unless
$P=NP$ the ratio provided by this simple algorithm cannot be improved!
\item Prove that for a general SAT formula, the expected number of
clauses that are satisfied is at least $m/2$ where $m$ is the number
of clauses.
\end{enumerate}
\end{enumerate}
\vspace{1in}
\vspace{1in}
%\newpage
{\bf The remaining problems are for self study. Do \emph{NOT} submit for grading.}
\begin{itemize}
\item See Jeff's homework 11 from Spring 2016. \url{https://courses.engr.illinois.edu/cs473/sp2016/hw/hw11.pdf}
\end{itemize}
\end{document}