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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{15. May 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}}



\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{Farkas' Lemma: Base Case}{10 Points}

Let $A \in \R^{m \times 1}$ and $\mathbf{b} \in \R^m$.
Suppose that there is no $x \in \R$ with $x \geq 0$ 
and $Ax \leq \mathbf{b}$.
Show that then there is a $\mathbf{y} \in \R^m$ with $\mathbf{y} \geq \mathbf{0}$, 
$\mathbf{y}^T A \geq 0$ and $\mathbf{y}^T \mathbf{b} < 0$.


\AUFGABE{Fourier-Motzkin Elimination I}{10 Points}

Consider the following system of linear inequalities with five
constraints and three variables.
\begin{align*}
 2x  - 5y  + 4z &\leq 10\\
 3x  - 6y + 3z &\leq 9\\
 5x  - 10y - z &\leq 15 \\
 -x  + 5y - 2z &\leq -7\\
 -3x + 2y + 6z &\leq 12\\
 x,y,z &\geq 0
\end{align*}
Use Fourier-Motzkin elimination to remove $x$.
Is the system feasible? 

\AUFGABE{Fourier-Motzkin Elimination II}{10 Points}

Describe an algorithm for solving LPs that
is based on Fourier-Motzkin elimination. Give a good
upper bound on the running time of your algorithm.

\emph{Hint}: The lemma from class deals only with the
feasibility of LPs. How can you get from the decision version
to the optimization?

\AUFGABE{Proof of Farkas' Lemma}{optional, 10 Extra Points}

Prove that the two alternatives in Farkas' Lemma cannot hold
simultaneously.
\end{description}
\end{document}
