\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{3 November 2014}{15}

\begin{center}
\Large{\bf Problem of the Week -- 11}
\end{center}

{\bf Feasibility and optimality}

Suppose you are given a {\em black box}\/ algorithm that takes as
input integers $n$, $m$, $m \times n$ matrix $A$ with integer entries,
and $m \times 1$ vector $b$ with integer entries, and returns whether
there exists a real $n \times 1$ vector $x$ such that $Ax \ge b$ (i.e,
the black box returns a yes or no answer).

You are faced with the following problem.  

\begin{center}
Find $x$ that minimizes $c^T x$ subject to the constraint $A' x \ge
b'$,
\end{center}

where $c$, $A'$, and $b'$ are $n' \times 1$ vector, $m' \times n'$
matrix, and $m' \times 1$ vector, all with integer entries,
respectively.  Show how to solve this problem by using the black box
algorithm, where the number of calls you make is at most polynomial in
$n'$, $m'$, and the sizes of $A'$, $b'$, and $c$.

\end{document}