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

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{am 09.\@ Juni 2015 vor der Vorlesung in die
  Mitarbeiterschachteln}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\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{\eps}{\varepsilon}


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

\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

\usepackage{xspace}
\newcommand{\OPT}{\ensuremath{\mathsf{{OPT}}}\xspace}

\usepackage{amsthm}
\theoremstyle{plain}
\newtheorem*{thm}{Satz}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER.\ Aufgabenblatt zur Vorlesung \hfill SoSe 2015

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Lena Schlipf, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

    \AUFGABE{Euklidisches TSP -- Schöne Instanzen} {10 Punkte}

    Eine Euklidische TSP Instanz $I$ besteht aus einem vollständigen Graphen
    $K_n=(V,V\times V)$, $V=\{v_1,\dots,v_n\} \subset \R^2$. Die Kosten einer
    Kante $\{v_i,v_j\}$ ist durch $\| v_i - v_j \|$
    gegeben.  Wir sagen $I$ ist \emph{sch\"on} falls
    \begin{enumerate}
        \renewcommand{\labelenumi}{(\roman{enumi})}
      \item F\"ur alle $v_i, v_j \in V$ gilt:
        $v_i \neq v_j \Rightarrow  \| v_i - v_j \| \geq 4$
      \item F\"ur alle $v \in V$ gilt: Die Koordinaten von $v$ sind ganzzahlig und
        im Intervall $[0, O(n)]$ enthalten.
    \end{enumerate}
    Sei $\eps > 0$. Angenommen wir haben ein PTAS f\"ur sch\"one Instanzen.
    Zeigen Sie, dass wir dann in Polynomialzeit eine $(1+\eps)$ Approximation
    f\"ur allgemeine Instanzen berechnen k\"onnen.

    \emph{Hinweis:} Transformieren Sie eine allgemeine ETSP Instanz in eine
    sch\"one ETSP Instanz. Sei dazu $Q$ das kleinste Quadrat, das alle Punkte
    enth\"alt und
    $L$ die Seitenl\"ange von $Q$. O.B.d.A.\ k\"onnen wir annehmen, dass die
    linke untere Ecke von $Q$ der Ursprung ist. Zeichnen Sie in $Q$ ein Gitter
    ein, das Abstand $\eps L/2n$ zwischen zwei horizontalen/vertikalen Linien
    hat und verschieben Sie die Punkte aus $P$ auf den n\"achstgelegenen
    Gitterpunkt. Wie ver\"andert sich dadurch \OPT? Skalieren Sie jetzt das
    Gitter um den Mindestabstand und ganzzahlige Koordinaten zu garantieren. Wie
    ver\"andert sich \OPT durch das Skalieren?

    \AUFGABE{Euklidisches TSP -- PTAS} {10 Punkte}

    Sei $I$ eine sch\"one Euklidische TSP Instanz.
    Betrachten Sie den folgenden Satz (Variablen und Begriffe wie in der
    Vorlesung):

    \begin{thm}
      Seien $\eps > 0$, $m=O(\frac{1}{\eps} \log L')$ und $r=O(1/\eps)$. Sei
      weiterhin $a,b \in (-L'/2, 0] \cap \Z$ zufällig gleichverteilt gewählt.
      Dann gilt:
      Mit Wahrscheinlichkeit mindestens $\frac{1}{2}$ gibt es bzgl.\ der
      $(a,b)$-Unterteilung von $I$ eine $r$-leichte Tor-ber\"ucksichtigende TSP
      Tour mit Kosten $\leq  (1+\eps) \OPT$.
    \end{thm}

    Zeigen Sie damit, dass der Algorithmus aus Satz~3.17 bez\"uglich der
    Parameter $m=O(\frac{1}{\eps} \log L')$ und $r=O(1/\eps)$ mit
    Wahrscheinlichkeit mindestens $\frac{1}{2}$ eine $(1+\eps)$-Approximation in $O(n
    \log^{O(1/\eps)} n)$ Zeit berechnet. Beschreiben Sie, wie der Algorithmus
    ver\"andert werden muss, um deterministisch eine $(1+\eps)$-Approximation in
    Polynomialzeit zu berechnen.

    \AUFGABE{Euklidisches TSP -- Untere Schranke für $\OPT$} {10 Punkte}

    Sei $I$ eine sch\"one Euklidische TSP Instanz und $T^*$ eine optimale TSP
    Tour f\"ur $I$.  F\"ur ein $i \in \Z$ bezeichne $v_i$ die vertikale Gerade
    $x = i$ und $h_i$ die horizontale Gerade $y = i$. Weiterhin sei $t(v_i)$
    bzw.\ $t(h_i)$ die Anzahl an Schnittpunkten von $T^*$ und $v_i$ bzw.\ $h_i$.
    Zeigen Sie:
    \begin{align*}
      \sum_{i \in \Z} t(v_i) + \sum_{i \in \Z} t(h_i) \leq 2 \OPT
    \end{align*}

    \emph{Hinweis}: Sei $\{v_1,v_2\}$ eine Kante in $T^*$ und $p_1=(x_1,y_1)$,
    $p_2=(x_2,y_2)$ die zugeh\"origen Punkte. D.h.\ die Kante hat Kosten $c =
    \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$. Wie viele Geraden $v_i$ bzw.\ $h_i$
    schneidet die Strecke $\overline{p_1 p_2}$ maximal? Sch\"atzen Sie dies dann
    mit $2c$ ab. Dabei kann folgende Ungleichung (mit Beweis!) hilfreich sein:
    \begin{align*}
      |x_1 - x_2| + |y_1 - y_2 | \leq \sqrt{2 \Big((x_1 - x_2)^2 + (y_1 - y_2)^2
        \Big)}.
    \end{align*}

\end{description}
\end{document}
