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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{bis zum 02. Mai 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\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{\R}{\mathbb{R}}



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


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

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\hfill SoSe 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost 

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Quadratisches Programmieren}{10 Punkte}

Angenommen, wir lassen in den Nebenbedingungen eines
linearen Programms auch Summanden der Form $d_{ij} x_j^2$
zu, mit $d_{ij} \in \R$.
Zeigen Sie, dass das resultierende algorithmische Problem
NP-schwer ist.

\AUFGABE{Varianten von LPs}{10 Punkte}

In der Vorlesung haben wir lineare Programme als Optimierungsprobleme der Form
\begin{align*}
\max c^Tx&, \text{ wobei}\\
Ax&\leq b\\
x &\geq 0
\end{align*}
definiert.
Zeigen Sie f\"ur jede der folgenden Varianten und Verallgemeinerungen, dass sie sich
auf ein LP obigen Form zur\"uckf\"uhren l\"asst:
\begin{enumerate}
  \item die Zielfunktion hat die Form $\min c^T x$,
  \item es gibt eine Nebenbedingung der Form $a_i x \geq b$,
  \item es gibt eine Nebenbedingung der Form $a_i x = b$,
  \item die Variable $x_i$ kann positiv oder negativ sein,
  \item es gibt eine Nebenbedingung der Form $x_i \geq |x_j|$.
\end{enumerate}


\AUFGABE{Dualit\"at von LPs}{10 Punkte}

Sei $G = (V, E)$ ein bipartiter Graph.
Eine \emph{Paarung} ist eine Menge $M \subseteq E$ von
Kanten, so dass jeder Knoten von $G$ h\"ochstens eine inzidente
Kante in $M$ hat. Eine \emph{Maximum-Paarung} ist eine Paarung
mit der gr\"o\ss{}tm\"oglichen Anzahl von Kanten.

\begin{enumerate}
  \item Zeichnen Sie einen bipartiten Graphen mit
    $10$ Knoten, der eine Maximum-Paarung mit $5$ Kanten enth\"alt.
    Ihr Graph soll auch eine \emph{maximale} Paarung mit $4$ Kanten
    enthalten, die keine Maximum-Paarung ist. (Eine Paarung $M$ hei\ss{}t
    \emph{maximal}, falls es keine Paarung $M'$ mit $M' \supset M$ und
    $M' \neq M$ gibt).
  \item Formulieren Sie das Problem, zu einem gegebenen bipartiten
    Graphen $G$ eine Maximum-Paarung zu finden, als lineares Programm.
    Erkl\"aren Sie Ihr lineares Programm kurz in Worten.
  \item
    Formulieren Sie das duale lineare Programm zu Ihrem linearen Programm 
    aus (b). Interpretieren Sie das Ergebnis.
  \item
    Informieren Sie sich \"uber den \emph{Satz von K\"onig}.
    Folgt der Satz schon aus (b) und (c)? Begr\"unden Sie Ihre Antwort.
\end{enumerate}


\end{description}
\end{document}
