\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{12. June 2017, in class.}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\eps}{\varepsilon}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Problem Set for 

\smallskip
\noindent
\large
\textbf{Advanced Algorithms II}\hfill Spring 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost 

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Set Cover I} {10 Points}

In this problem, we will see a simple analysis
of the greedy approximation algorithm for the 
unweighted set cover problem.  Let $X = \{x_1, 
\dots, x_n\}$ be a set and $S = \{S_1, \dots,
S_k \}$ a set of subsets of $X$. Recall that 
the greedy algorithm iteratively picks a set 
that covers the largest number of uncovered
elements. Let $\text{OPT}$ be an optimal set 
cover for $X$.

\begin{enumerate}
    \item Let $n_j$, $j \geq 0$, be the number of 
      uncovered elements after the greedy algorithm
      has chosen $j$ sets. Show that the $(j+1)$th 
      set will cover at least $n_j/|\text{OPT}|$ new elements
      in $X$.
    \item Show that for $j \geq 0$, we have 
      $n_{j+1} \leq (1-1/|\text{OPT}|)n_j$.
    \item Conclude that the greedy algorithm uses at most
      $|\text{OPT}|\ln n$ sets.
\end{enumerate}

\AUFGABE{Set Cover II} {10 Points}

Let $X = \{x_1, \dots, x_n\}$ be a set and 
$S = \{S_1, \dots,S_k \}$ a set of subsets of
$X$. Furthermore, let $w: S \rightarrow  \R^+$ be
a weight function.  The \emph{weight}
of a set cover $S' \subseteq S$ is 
$w(S') = \sum_{S_j \in S'} w(S_j)$. The goal
is to find a set cover of minimum weight.

\begin{enumerate}
  \item Let $\mathcal{A}$ be the greedy approximation algorithm for
    \textsc{SetCover} from class, and let 
    $m = \max \{|S_i| \mid S_i \in S\}$. Show that $\mathcal{A}$ 
    computes an $H_m$-approximation for the weighted set cover
    problem.
  \item
    For any given $n$ and $\eps > 0$, construct an input $X$, $S$, 
    $w$ for \textsc{SetCover} with $|X| = n$, so that $\mathcal{A}$
    will find a set cover with weight 
    exactly $H_n$, even though there is a set cover of cost at most 
    $1 + \eps$. Whenever the algorithm has a choice
    between different sets, you may assume that it makes the worst
    possible choice.
    How does your result relate to part (a)?
\end{enumerate}

\AUFGABE{Vertex Cover}{10 Points}

\begin{enumerate}
  \item Let $T = (V, E)$ be a tree. 
    Give a greedy algorithm that finds a minimum vertex cover for
    $T$ in $O(|V|)$ time.
  \item Let $\mathcal{A}$ the greedy approximation algorithm for 
    \textsc{VertexCover} from class. For any given $n$,
    construct a graph $G$ with $n$ nodes such that 
    $\mathcal{A}$ applied to 
    $G$ returns a vertex cover with $2 |\text{OPT}|$ nodes.
    You may assume that the algorithm always makes the
    worst possible choice.
\end{enumerate}

\end{description}
\end{document}
