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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{02. May 2017, 12:00, in
the mailbox next to room 111}

\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}}



\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{Quadratic Programming}{10 Points}

Suppose that in the constraints of a linear program,
we also allow summands of the form $d_{ij} x_j^2$, for
$d_{ij} \in \R$.
Show that the resulting algorithmic problem is NP-hard.

\AUFGABE{Variants of LPs}{10 Points}

In class, we defined a linear program as a constrained
optimization problem of the following form
\begin{align*}
\max c^Tx&, \text{ subject to}\\
Ax&\leq b\\
x &\geq 0.
\end{align*}
Show that the following variants and generalizations can all
be reduced to an LP of this form:
\begin{enumerate}
  \item the objective function is of the form $\min c^T x$,
  \item there is a constraint of the form $a_i x \geq b$,
  \item there is a constraint of the form $a_i x = b$,
  \item the variable $x_i$ may be positive or negative,
  \item there is a constraint of the form $x_i \geq |x_j|$.
\end{enumerate}


\AUFGABE{LP-Duality}{10 Points}

Let $G = (V, E)$ be a bipartite graph.
A \emph{matching} is a set $M \subseteq E$ of
edges such that each vertex in $G$ is incident to at
most one edge in $M$. A \emph{maximum matching} is a
matching of maximum cardinality.

\begin{enumerate}
  \item Draw a bipartite graph with
    $10$ vertices that has a maximum matching with $5$ edges.
    Your graph should also contain a \emph{maximal} matching
    with $4$ edges.
    (A matching $M$ is \emph{maximal} if there is no matching $M'$ with,
    $M' \supset M$ and $M' \neq M$.)
  \item Give an LP-formulation for the problem of finding
    a maximum matching in a bipartite graph $G$.
    Briefly explain your LP in words.
  \item
    Give the dual LP for your LP from (b). Interpret the result.
  \item
    Read up on \emph{K\"onig's theorem}.
    Is the theorem already implied by your results from (b) and (c)?
    Explain.
\end{enumerate}


\end{description}
\end{document}
