\documentclass[unbewertet]{agisuebung}

\date{17.~Dezember 2024}
%\newcommand{\deadlineDate}{Mittwoch, 06.~November 2024, 12:15~Uhr}
\newcommand{\exerciseNum}{3}
\usepackage{multicol}

% # # # # # # # # # # # # # # # # # # # # # # # # # #
\begin{document} %  # # # # # # # # # # # # # # # # #
% # # # # # # # # # # # # # # # # # # # # # # # # # #


% ### aufgabe
\begin{aufgabe}[1D-Zooming] % ------------------------------------------------
Betrachtet man Kartenbeschriftung in 1D, so werden Labels als offene Intervalle auf der
$x$-Achse repräsentiert, die jeweils an einem festen Punkt verankert sind. Während das Zoomen
eines Labels im zweidimensionalen Fall durch eine Pyramide im Raum beschrieben werden kann,
beschreibt man das Zoomen eines Labels im eindimensionalen Fall entsprechend als Dreieck in
der Ebene:

{\centering\includegraphics{figures/1d-zoom}}

Betrachten Sie das Problem \textsc{1DZooming}:

\textbf{Gegeben:} Menge $\mathcal{L}$ von (offenen) Labeldreiecken mit verfügbaren Intervallen $(0,S_L)$ für alle $L\in \mathcal{L}$

\textbf{Gesucht}: Aktive Intervalle $(0,A_L)$ für alle $L\in\mathcal{L}$, so dass $\sum_{L\in\mathcal{L}} A_L$ maximiert wird.

\begin{teilaufgabe}
	\item Stellen Sie ein dynamisches Programm auf, das \textsc{1DZooming} optimal löst.
	\item Funktioniert Ihr dynamisches Programm auch, wenn nicht verlangt wird, dass die aktiven Intervalle bei 0 beginnen?
	\item Überlegen Sie sich einen Anwendungsfall für das eindimensionale Zoomen.
\end{teilaufgabe}
\end{aufgabe}

\clearpage

\begin{aufgabe}[Schubfachprinzip]
Zeigen Sie folgende Aussagen mit Hilfe des Schubfachprinzips.
\begin{teilaufgabe}
 \item Sei $S\subseteq\{1,\ldots,100\}, |S|=51$ eine Menge von 51 unterschiedlichen ganzen Zahlen zwischen 1 und 100.

	Zeigen Sie, dass es in $S$ mindestens zwei aufeinander folgende Zahlen gibt.
 \item Sei $T\subseteq\{1,\ldots,100\}, |T|=10$ eine Menge von 10 unterschiedlichen ganzen Zahlen zwischen 1 und 100.

	Zeigen Sie, dass es zwei verschiedene nicht-leere Teilmenge $T_1\subseteq T,T_2\subseteq T, T_1\neq T_2$ von $T$ gibt, so dass $\sum_{x\in T_1} x=\sum_{x\in T_2} x$.
\end{teilaufgabe}
\end{aufgabe}

\begin{aufgabe}[Statische Kartenbeschriftung mit Line Stabbing]
Betrachten Sie das statische Beschriftungsproblem im 1P Model. Nehmen Sie an, dass alle Label gleich hoch sind.

Geben Sie einen Faktor-$(1/2)$-Approximationsalgorithmus für das Problem an.
\end{aufgabe}

\begin{aufgabe}[EPTAS für \textsc{LabelRotationMaxTotal}]
Wir wollen den Approximationsfaktor des EPTAS für \textsc{LabelRotationMaxTotal} beweisen.
Seien $k=\lceil 2/\varepsilon\rceil$, $\mathcal{L}$ die gegebenen Label, $\mathcal{A}$ die Lösung des EPTAS und $\mathcal{O}$ die optimale Lösung. Wir schreiben vereinfacht $|A|=\min_L|A_L|$ für die Gesamtlänge aller aktiven Bereiche in einer Beschriftung $A$.

Wir unterteilen $\mathcal{L}$ in $k^2$ Gruppen $\mathcal{L}_{i,j}, 0\le i,j< k$.
Jede Gruppe $\mathcal{L}_{i,j}$ enthält genau die Label, die eine $i$-te vertikale und $j$-te horizontale Linie (modulo $k$) schneidet.

Jede Teilinstanz, die der Algorithmus bildet, kann dann durch $\mathcal{L}^{a,b}=\cup_{i\neq a, j\neq b}\mathcal{L}_{i,j}$ beschrieben werden, also indem man alle Labels entfernt, die eine $a$-te vertikale oder eine $b$-te horizontale Linie (modulo $k$) schneiden.

Sei nun $\mathcal{A}^{a,b}$ die (optimale) Lösung des Algorithmus für die Teilinstanz $\mathcal{L}^{a,b}$. Wir definieren genauso $\mathcal{O}^{a,b}=\mathcal{O}\cap \mathcal{L}^{a,b}$ und $\mathcal{O}_{i,j}=\mathcal{O}\cap \mathcal{L}_{i,j}$. 

\begin{teilaufgabe}
	\item	Zeigen Sie: $|\mathcal{A}^{a,b}|\ge \sum_{i\neq a, j\neq b}|\mathcal{O}_{i,j}|$ für alle $0\le a,b<k$.
	\item	Zeigen Sie: $\sum_{0\le a,b<k}|\mathcal{A}^{a,b}|\ge (k-1)^2 |\mathcal{O}|$.
	\item	Zeigen Sie: Der Algorithmus ist eine $\frac{(k-1)^2}{k^2}$-Approximation.
	\item	Zeigen Sie: Der Algorithmus ist eine $(1-\varepsilon)$-Approximation.
\end{teilaufgabe}
\end{aufgabe}


% # # # # # # # # # # # # # # # # # # # # # # # # # #
\end{document} %  # # # # # # # # # # # # # # # # # #
% # # # # # # # # # # # # # # # # # # # # # # # # # #