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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{26. 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{\Z}{\mathbb{Z}}
\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{Arora's PTAS: The Number of Interfaces}{10 points}

\begin{enumerate}
\item Let $S$ be a sequence of  $2a$ portals, arranged on the
boundary of a cell $C$. A \emph{plane perfect matching}
on $S$ is a set of $a$ pairwise disjoint curves in $C$ with
endpoints in $S$ (there are no crossings and no common endpoints).
Let $C_a$ be the number of plane matchings on $2a$ portals.
Argue that 
\[
  C_0 = 1, \text{ and } C_a = \sum_{j = 0}^{a-1} C_j C_{a-1-j},
  \text{ for }  a \geq 1.
\]
\item Let $f(x) = \sum_{a = 0}^\infty C_a x^a$ be the 
\emph{generating function} for $(C_a)_{a \in \N}$.
Show that $f$ obeys the functional equation
$f(x) = 1 + xf(x)^2$.
\item Show that \[
  f(x) = \frac{1 - \sqrt{1-4x}}{2x}.
\]
\emph{Hint}: We need $\lim_{x \rightarrow 0^+} f(x) = 1$.
\item
Define
\[
\binom{\frac{1}{2}}{n} = \frac{\prod_{i = 0}^{n-1} (1/2 - i)} {n!}.
\]
Show that 
\[
\binom{\frac{1}{2}}{n} = \frac{(-1)^{n+1}}{4^n(2n-1)}\binom{2n}{n}.
\]
\item
It is known that for $|y|$ small enough, 
$\sqrt{1+y} = \sum_{n = 0}^\infty \binom{\frac{1}{2}}{n} y^n$.
Show that
\[
f(x) = \sum_{a = 0}^\infty \binom{2a}{a}\frac{x^a}{a+1}.
\]
\item
Conclude that the number of possible interfaces during the
dynamic programming phase of Arora's PTAS is
$2^{O(m)}$.
\end{enumerate}

\AUFGABE{Arora's PTAS: Portal-Respecting Tours}{10 points}

For every $n \in \N$,
give a nice instance of Euclidean TSP where the process
of making an optimal tour $\pi$ portal-respecting increases the 
length of $\pi$ by at least a fixed constant factor, independent 
of $\eps$ and $n$.

\AUFGABE{Arora's PTAS: Bounding $\text{OPT}$}{10 points}

Let $Q = \{q_1, \dots, q_n\}$ be a nice instance for
Euclidean TSP, and let $\pi$ be an optimal tour for 
$Q$.
For $i \in \{0, \dots, L\}$, let $v_i$ be the vertical line
$v_i: x = i$ and $h_i$ the horizontal line $h_i y = i$.
Furthermore, let $t(v_i)$ and $t(h_i)$ 
be the number of intersections between $\pi$ and $v_i$ and $h_i$.
Show that
\[
\sum_{i = 0}^L t(v_i) + \sum_{i = 0 }^L t(h_i) \leq 4 \text{OPT}.
\]

\emph{Hint}: Let $e = q_1q_2$ be an edge of $\pi$, and let $q_1=(x_1, y_1)$
and $q_2=(x_2,y_2)$. This means that the length of $e$ is 
$c = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$. 
Argue that $e$ intersects at most $|x_1 - x_2| + |y_1 - y_2| + 2$
lines $h_i$, $v_i$, $i \in \{0, \dots, L\}$. Bound this by $4c$. 

You may find the following inequality useful (prove it).
For all $a, b \geq 0$, we have
\[
a + b \leq \sqrt{2 (a^2 + b^2)}.
\]

\end{description}
\end{document}
