\documentclass[a4paper,12pt]{scrartcl}

% \usepackage[english,german]{babel} % [verfuegbare Sprachen, letzgenannte ist aktiv]
\usepackage{tikz}
\usetikzlibrary{arrows,positioning} 

\usepackage{graphicx} % include eps graphics
\usepackage{psfrag} % .eps properly aligned, scaled, and rotated
\usepackage{wrapfig} % WRAP FIGURE [text umfliest das Bild]
\usepackage[ngerman,english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\usepackage{mathtools}
\usepackage{ngerman} % Silbentrennung ect. in neuer-Rechtschreibung-deutsch
\usepackage{eurosym} % Das euro Symbol [nicht mehr]
\usepackage{color} % textcolors [RGB oder auch 68 Standardfarben]
\usepackage{soul}
\usepackage{enumerate} % aufzaehlungen
\usepackage{paralist} % kuerzere Aufzaehlungen
\usepackage{url} % bessere Darstellung (hyperref: auch anklickbar)
\usepackage{alltt} % ermoeglicht uninterpretierten Text (sozusagen String)
\usepackage{ae,aecompl} % ecFonts auf cmFonts zurueckfuehren
\usepackage{ifthen}
\usepackage{amsmath} % MATH allignment[Matrix,Brueche,Gleichungen]
\usepackage{amssymb} % Mathe SYMBOLE
\usepackage{amsthm} % Mathe THEOREM [theorem,lemma,proof] Gliederung
\usepackage{verbatim} % multiline comment
\usepackage{paralist}
\parindent =0pt
\usepackage{geometry}
\graphicspath{{../../figures/}}
\geometry{
  body={},
  left=1.2in,
  right = 1.2 in,
  top=1.25in
}
\hypersetup{
  colorlinks = true,
  urlcolor = red,
  pdfauthor = {},
  pdfkeywords = {albert haase, mathematics, mathematik},
  pdfsubject = {},
  pdfpagemode = UseNone
}

\newcommand{\R}{\mathbb{R}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\s}{\mathbb{S}}
\newcommand{\su}{\mathcal{S}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\ti}{\mathcal{T}}
\newcommand{\cc}{\mathcal{C}}
\newcommand{\dd}{\mathcal{D}}
\newcommand{\E}{\mathbf{E}}
\newcommand{\HRule}{\rule{1.03\textwidth}{0.5mm}}
\renewcommand\O{\mbox{\rm O}}
%\renewcommand{\subset}{\subseteq}
\newcommand{\V}{\mathcal{V}}
\DeclareMathOperator{\im}{im}
\newcommand\Stack{\mathrm{Stack}}
\renewcommand{\to}{\longrightarrow}


\newcommand{\red}{\textcolor{red}} %Farben
\newcommand{\green}{\textcolor{green}}
\newcommand{\ink}{\textcolor[rgb]{0,.2,.8}}
\newcommand{\purp}{\textcolor[rgb]{0.9,0,.5}}
\newcommand{\sky}{\textcolor[rgb]{0,.5,.7}}
\newcommand{\tree}{\textcolor[rgb]{0,.4,.1}}
\newcommand\Emph[1]{\emph{\color{blue}#1}}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\VV}{\mathcal{V}}

\newcommand{\set}[1]{\ensuremath{ \left\{ #1 \right\}}}
\newcommand{\mset}[2]{\ensuremath{\left\{ #1  :  #2 \right\}}}
\renewcommand{\mapsto}{\longmapsto}
\newcommand{\inner}[1]{\left\langle \, #1  \,\right\rangle}
\newcommand{\linspan}[1]{\ensuremath{\text{span}\left\{ #1 \right \} }}
\newcommand{\ma}{\begin{smallmatrix} } \newcommand{\trix}{\end{smallmatrix}} % Matrix
\newcommand\aff{\operatorname{aff}}
\newcommand\conv{\operatorname{conv}}
\DeclareMathOperator{\cone}{cone}
\DeclareMathOperator{\inter}{int}
\linespread{1.1}

\selectlanguage{german}
\tikzset{
>=stealth',
pil/.style={
           ->,
           shorten <=1pt,
           shorten >=1pt,}
}

\begin{document}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushleft}
\includegraphics[scale=0.09]{bms-logo-eff}\\[5pt]
{\small Prof.~G\"unter M.~Ziegler} \\
{\small Albert Haase, Marie Litz}
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
\includegraphics[scale=0.4]{fu-logo}\\[5pt]
{\small Institut f"ur Mathematik }\\
{\small Arbeitsgruppe Diskrete Geometrie}\\
\end{flushright}
\end{minipage}

\enlargethispage{5mm}
\vspace{20pt}
\centerline{\Large \bf{Discrete Geometry II -- Problem Sheet 2}}
\vspace{15pt}

Please hand in your solutions to Prof.~Ziegler on \textbf{Tuesday, May.~6, 2014} before the lecture begins. 

\vspace{20pt}
{\large\bf Problem 1: }\textit{Transforming models}\hfill (4 Points)\\[3pt]
Assume we are given the following model (``Model 1'') of a linear program
\[
\mathrm{(P)}:\quad \begin{Bmatrix*}[r]
\max & c^t x & \\
& Ax & \le & b \\
\end{Bmatrix*}
\]
where $A$ has $n$ rows and $d$ columns.
\begin{compactenum}[\normalfont (a)]
\item
Describe a method to transform linear programs in Model 1 into the following form (``Model 2''):
\[
\mathrm{(P)}:\quad 
\begin{Bmatrix*}[r]
 By & = & f \\
y & \geq & 0
\end{Bmatrix*}.
\]
How many variables and equalities do we now have? 
\item Show that every Model 2 of (P) can be transformed into the form of Model 1.
\item 
If we use your transformation of Model 1 into the form of Model 2,
and then transform the resulting system back into form of Model 1, how many variables and inequalities do we 
then have?
\end{compactenum}

\vspace{10pt}

{\large\bf Problem 2: }\textit{Complexity issues}\hfill (8 Points)\\[3pt]
Let $A\in\{0,1,-1\}^{n\times n}$ be a $0/{\pm} 1$ matrix. Show that
\begin{compactenum}[\normalfont (a)]
        \item The determinant of $A\in\{0,1\}^{n\times n}$ can be arbitrarily large, 
        even if there are only two $1$'s per row.
        \item The determinant of $A\in\{0,1,-1\}^{n\times n}$ is 
          bounded if there is at most one $1$ and at most one $-1$ per row.
        \item Use the Hadamard inequality to give an upper bound for $|\det A|$.
        \item Assume now that $A\in\{0,1\}^{n\times n}$. Give a much better upper bound by 
        \begin{compactitem}[---] 
                \item multiplying the matrix by $2$,
                \item adding a column of $0$'s and then a row of $1$'s,
                \item subtracting the newly added row from all others,
        \end{compactitem}
            and then applying the Hadamard inequality to the resulting $\pm1$-matrix.
        \item Give an example where the bound in (d) is tight.
\end{compactenum}
{\large\bf Problem 3: }\textit{Network flows and integer programs}\hfill (8 Points)\\[3pt]
Assume we are given a finite network $D = (V,A)$ with source and sink and with integer-valued 
arc capacities. That is, $D$ is a finite directed graph with finitely 
many vertices where each arc $(x,y) \in A$ has a capacity $c(x,y) \in \Z_{\geq 0}$. 
Additionally, there are two distinguished vertices $s,t \in V$ called the \emph{source} 
and the \emph{sink}. A \emph{flow} $f$ through the network $D$ is a function 
$f\colon V \times V \to \R$ such that for all $(x,y) \in A$ we have $0\le f(x,y) \le c(x,y)$. 
Furthermore ``flow conservation'' is required to hold at each vertex $v\in V\setminus\{s,t\}$,
that is, the sum of the flow values on arcs into such a vertex equals the sum of the
flow values on arcs leaving the vertex.
Our goal is to measure the total flow, which can be calculated as the sum of the
values of $f$ on all the arcs that leave the source.
%See e.g.~\emph{Wikipedia} for more details.
 
%\begin{figure*}[h!]
\begin{center}
\begin{tikzpicture}
  [scale=1]
  \node[circle,draw,thick] (a) at (0,4) {$a$};
  \node[circle,draw,thick] (b) at (2,6) {$b$};
  \node[circle,draw,thick] (c) at (3,2) {$c$};
  \node[circle,draw,thick] (d) at (6,5) {$d$};
  \node[circle,draw,thick] (e) at (6,3) {$e$};
  \node[circle,draw,thick] (f) at (8,2) {$f$};
  \node[circle,draw,thick] (g) at (9,7) {$g$};
  \node[circle,draw,thick] (h) at (10,4) {$h$};
  \draw[black, pil] (a) -- (b) node[pos=0.4,above] {4};
  \draw[black, pil] (a) -- (c) node[pos=0.5,above] {2};
  \draw[black, pil] (a) -- (d) node[pos=0.5,above] {2};
  \draw[black, pil] (b) -- (d) node[pos=0.6,above] {2};  
  \draw[black, pil] (b) -- (g) node[pos=0.5,above] {1};
  \draw[black, pil] (c) -- (e) node[pos=0.5,above] {3};
  \draw[black, pil] (d) -- (g) node[pos=0.5,above] {4};
  \draw[black, pil] (d) -- (h) node[pos=0.5,above] {2};
  \draw[black, pil] (e) -- (d) node[pos=0.5,right] {1};
  \draw[black, pil] (c) -- (e) node[pos=0.5,above] {3};
  \draw[black, pil] (g) -- (h) node[pos=0.5,right] {3};
  \draw[black, pil] (e) -- (f) node[pos=0.5,above] {2};
  \draw[black, pil] (f) -- (h) node[pos=0.5,above] {2};
  \draw[black, pil] (f) -- (c) node[pos=0.5,above] {1};
\end{tikzpicture}
\\%\caption
{Example of a network with source ``$a$'' and sink ``$h$'' and integer capacities as indicated by the labels of the edges.}
\end{center}
%\end{figure*}

\vspace{20pt}

\begin{compactenum}[\normalfont (a)]
\item 
%In the first tutorial we saw in an example how to construct a linear program to determine the maximal flow through a network.%\footnote{An alternative would have been to apply the max-flow min-cut theorem.} 
Describe a linear program to determine the maximal flow for a network $D$ as introduced above.
%\item Convert the result from (a) into the matrix form $\mathrm{(P)}\colon Ax \le b$.
      How many rows and columns do you need --- for the example given in the figure, and for a 
      general network? % for the  matrix in (b)?
      
      What numbers can occur as matrix entries? 
      
  What is the form of your LP from (a)? Is it one of the ``models'' in Problem 1?
 
\item Describe and interpret the dual linear program.

\item
What type of matrix is~$A$? 

Show that the feasible basic solutions of (P) are in fact integral.
\end{compactenum}


\end{document}


