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

\newcommand{\ZETTELNUMMER}{9}
\newcommand{\ABGABEDATUM}{19. 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{MAX-3SAT} {10 points}

MAX-3SAT is the following problem:
suppose we have a propositional formula 
\[
  \Psi = C_1 \wedge C_2 \wedge \dots \wedge C_m
\]
in CNF with $n$ variables and $m$ clauses, 
such that each clause contains exactly three
literals with pairwise distinct variables.
Our task is to find an assignment $\alpha: \{x_1, \dots, x_n\}
\rightarrow \{0,1\}$ that satisfies the maximum number 
of clauses.
\begin{enumerate}
    \item Show that MAX-3SAT is NP-hard.
    \item Show that there is always an assignment
      $\alpha$ that satisfies at least $(7/8)m$
      clauses.
    \emph{Hint}: Consider a random $\alpha$.
    \item For any $\eps > 0$, give a Las-Vegas 
      approximation algorithm that provides a 
      $(7/8 -\eps)$-approximation for MAX-3SAT and runs in 
      expected polynomial time.
    \item (\emph{extra credit, 5 points}) Give a Las-Vegas 
      approximation algorithm that provides a $7/8$-approximation 
      for MAX-3SAT and runs in expected polynomial time.
\end{enumerate}


\AUFGABE{Metric $st$-TSP: Hoogeveen's algorithm}{10 points}

Let $V = \{1, \dots, n\}$ be a set of
vertices, and let $d: \{1, \dots, n\} \times \{1, \dots, n\}
\rightarrow \R_{\geq 0}$ be a metric on $V$.
Let $s, t \in V$ be two distinct vertices.
A \emph{TSP-path} from $s$ to $t$ is
a path that starts in $s$, ends in $t$, and visits
every vertex from $V$ exactly once.
In the \emph{metric $st$-TSP-problem}, we are looking
for a TSP-path from $s$ to $t$ of minimum total length.

\begin{enumerate}
  \item Adapt the Christofides heuristic for the metric
   $st$-TSP-problem.

  \emph{Hint}: An \emph{Eulerian $st$-path} is a
   path that starts in $s$, ends in $t$, and visits
   every edge exactly once. A connected graph contains an Eulerian
   $st$-path if and only if $s$ and $t$ are the only vertices
   with odd degree. Compute an MST $T$ for $K_n$ with edge
   lengths $d(i,j)$ and set $W$ to the set of all vertices
   with ``wrong'' degree in $T$. Let $M$ be a minimum cost
   perfect matching for $W$. Proceed as in the Christofides heuristic.

  \item Let $\Pi_{st}$ be an
    optimal TSP-path from $s$ to $t$. 
    Show that 
    $w(T) \leq w(\Pi_{st})$.

   \item 
   Let $F$ be the
   edge \emph{multiset} $T \cup \Pi_{st}$.
   Argue that the set of vertices with odd degree
   in $(V, F)$ is exactly $W$.

  \item Let $w_1, w_2, \dots, w_{2m}$ be the
    vertices of $W$ in the order as they appear 
    in $\Pi_{st}$.
    For $i = 1,\dots m$, let
    $F_i$ be the sequence of edges on 
    $\Pi_{st}$ between $w_{2i-1}$ and $w_{2i}$.
    Argue that $w(M) \leq \sum_{i = 1}^m w(F_i)$.

  \item Let 
    $F' = F \setminus \bigcup_{i = 1}^m F_i$.
    Argue that $(V, F')$ is Eulerean. Conclude that
    there are two perfect matchings $M_1$ and $M_2$ on $W$ with
    $w(M_1) + w(M_2) \leq w(F')$. 

  \item Conclude that $3w(M) \leq w(F) \leq 2w(\Pi_{st})$, and
   that the algorithm gives a $5/3$-approximation for the minimum
   $st$-TSP-problem.
\end{enumerate}

\AUFGABE{Nice Inputs for Euclidean TSP} {10 points}

Prove the lemma from class that in order to obtain a PTAS for 
Euclidean TSP, it suffices to consider nice inputs.

Suppose that for each fixed $\eps > 0$, 
there exists an algorithm $\mathcal{A}$ with 
the following property: given $n \in \N$, such that $n$
is a power of two, and a set
$Q$ of at most $n$ vertices of the $4n^2 \times 4n^2$ grid,
the algorithm $\mathcal{A}$ runs for $n^{O(1/\eps)}$ steps and
returns a TSP tour for $Q$ with length at most
$(1 + \eps)\text{OPT}_Q$.

Then, for each $\eps > 0$, there is an algorithm 
$\mathcal{A}'$ with 
the following property: given a set
$P \subset \R^2$ of $n$ points in the plane,
the algorithm $\mathcal{A}'$ runs for $n^{O(1/\eps)}$ steps and
returns a TSP tour for $P$ with length at most
$(1 + \eps)\text{OPT}_P$.


\end{description}
\end{document}
