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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{08. 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{Bit Complexity}{10 Points}

\begin{enumerate}
	\item
  	  Let $x$ be a integer that can be represented with $a$ bits and
	  $y$ an integer that can be represented with  $b$ bits.
	  How many bits are needed at most to represent $x+y$? Explain.
	\item
  	  Let $x$ be a integer that can be represented with $a$ bits and
	  $y$ an integer that can be represented with  $b$ bits.
	  How many bits are needed at most to represent $x\cdot y$? Explain.
        \item
		Let $A = (a_{ij})$ be an $n \times n$ matrix, such that
		all entries of $A$ can be represented with $a$ bits.
		The \emph{determinant} of $A$, $\text{det}(A)$, is given
		by
		\[
			\text{det}(A) = \sum_{\sigma \in S_n} \text{sgn}(\sigma) \prod_{i = 1}^n a_{i\sigma(i)},
		\]
		where $S_n$ denotes the set of all permutations of $\{1, \dots, n\}$.
	        Give a good upper bound on the number of bits needed to represent
		$\text{det}(A)$. Explain your answer.
\end{enumerate}

\AUFGABE{Ellipsoid Algorithm}{10 Points}

Let $L: \max \mathbf{c}^T\mathbf{x}, A\mathbf{x} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}$, be a linear program
with $n$ variables and $m$ constraints.
A \emph{efficient separation oracle} for $L$ is a poynomial-time algorithm
that does the following: given a candidate solution $\mathbf{x} \in \R^n$
with $\mathbf{x} \geq 0$,
either (i) assert (correctly) that $\mathbf{x}$ is feasible for $L$, or
(ii) produce a constraint of $L$ that certifies that $\mathbf{x}$ is not
feasible, i.e., a row $j$ of $A$ such that $\mathbf{a}_j \cdot \mathbf{x} > \mathbf{b}$.

\begin{enumerate}
  \item Explain the following statement: ``If an efficient separation oracle
	  is available, then the ellipsoid algorithm runs in polynomial time.''
  \item The \emph{minimum cost aroborescence} problem problem is as follows:
	  given a directed graph $G = (V,E)$, a \emph{root} $r \in V$, and
	  a positive \emph{cost} $c_e$ for each edge $e \in E$, find a 
	    subset $F \subseteq E$ of directed edges such that
	    (i) $(V, F)$ contains a directed path from $r$ to every other vertex, and
	    (ii) the total cost of $F$ is minimized.
	    Edmonds showed that this problem is captured by the following LP:
	    \begin{align*}
		    &\min \sum_{e \in E} c_e x_e, \text{subject to}\\
			 &\sum_{\substack{(u,v) \in E,\\ u \in  S, v \in V \setminus S}}
		    x_e \geq 1, \text{for all } S \subseteq V \text{ with } r \in S\\
		    &x_e \in [0,1], \text{ for all } e \in E.
	    \end{align*}
	    What is the number of constraints of this LP? Show that the minimum cost arborescence 
            problem can be solved in polynomial time.
\end{enumerate}

\AUFGABE{Variants of Farkas' Lemma}{10 Points}

In class, we have seen the following variant of 
Farkas' lemma:
Let $A \in \R^{m \times n}$ and $\mathbf{b} \in \R^m$.
Then \emph{either} there is a $\mathbf{x} \in \R^n$ with
$\mathbf{x} \geq \mathbf{0}$ and $A\mathbf{x} \leq \mathbf{b}$,
\emph{or} there is a
$\mathbf{y} \in \R^m$ with $\mathbf{y} \geq \mathbf{0}$, 
$\mathbf{y}^T A \geq \mathbf{0}^T$ and 
$\mathbf{y}^T\mathbf{b} < 0$.

Prove that the following two statements are equivalent to
the lemma from class:

\begin{enumerate}
  \item Let $A \in \R^{m \times n}$ and $\mathbf{b} \in \R^m$.
    \emph{Either} there is an $\mathbf{x} \in \R^n$ with 
    $\mathbf{x} \geq \mathbf{0}$ and 
    $A\mathbf{x} = \mathbf{b}$, 
    \emph{or} there is a $\mathbf{y} \in \R^m$ with
       $\mathbf{y}^T A \geq \mathbf{0}^T$ and 
       $\mathbf{y}^T \mathbf{b} < 0$.
  \item Let $A \in \R^{m \times n}$ and $\mathbf{b} \in \R^m$.
    \emph{Either} there is an $\mathbf{x} \in \R^m$ with 
    $A\mathbf{x} \leq \mathbf{b}$, 
    \emph{or} there is an $\mathbf{y} \in \R^m$ with
       $\mathbf{y} \geq \mathbf{0}$,
       $\mathbf{y}^T A = \mathbf{0}^T$ and 
       $\mathbf{y}^T \mathbf{b} < 0$.
\end{enumerate}

\end{description}
\end{document}
