%---------change this every homework
\def\yourname{}
% -----------------------------------------------------
\def\homework{1} % 0 for solution, 1 for problem-set only
\def\duedate{wed may 4, 2016 at 5p}
\def\duelocation{via course website}
\def\hnumber{8}
\def\prof{abhi shelat}
\def\course{\href{https://www.cs.virginia.edu/~shelat/16s4102}{cs4102 - algorithms - s'16}}%------
%-------------------------------------
%-------------------------------------

\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.3,0.02,0.02} 
\definecolor{cit}{rgb}{0.05,0.2,0.45} 
\pagestyle{myheadings}
\markboth{\yourname}{\yourname}
\usepackage{clrscode}


\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\handout}{
   \renewcommand{\thepage}{H\hnumber-\arabic{page}}
   \noindent
   \begin{center}
      \vbox{
    \hbox to \columnwidth {\sc{\course} --- abhi shelat \hfill}
    \vspace{-2mm}
    \hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}H\hnumber.\yourname}}
      }
   \end{center}
   \vspace*{2mm}
}
\newcommand{\solution}[1]{\medskip\noindent\textbf{Solution:}#1}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{practice}{\sc\color{cit}practice}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}


\begin{document}
\thispagestyle{empty}
\handout
You may collaborate with other students on
  the homework but you must submit your own individually written
  solution, identify your collaborators, and acknowledge any
  external sources that you consult.  Do no submit a solution that you cannot explain to me.
All problems are related to maxflow/mincut.

\begin{problem}April in Paris\end{problem}
Lecture 27 will be in Paris! I'm sending all of you. Help me find the cheapest way to get all 135 of you there.  Here are flights and available seats.

\begin{center}\begin{tabular}{cccc|cccc}
			&				&		Seats	&	Price (\$)	&
			&				&		Seats	&	Price (\$)	
			\\
\textsc{cho}	&	\textsc{ord}	&		14		&	114 	&
\textsc{cho}	&	\textsc{iad}	&		74		&	64 \\
\textsc{cho}	&	\textsc{lga}	&		13		&	89 	&
\textsc{cho}	&	\textsc{atl}		&		24		&	72 \\
\textsc{cho}	&	\textsc{ctl}		&		44		&	90 \\
%
\textsc{iad}	&	\textsc{bru}	&		16		&	269 &
\textsc{iad}	&	\textsc{zrh}	&		78		&	536 \\
\textsc{iad}	&	\textsc{cdg}	&		15		&	555 &
\textsc{iad}	&	\textsc{mla}	&		13		&	480 \\
%
\textsc{ord}	&	\textsc{lhr}		&		61		&	309 &
\textsc{ord}	&	\textsc{cdg}	&		23		&	390 \\
\textsc{ord}	&	\textsc{fra}	&		61		&	412 &
\textsc{ord}	&	\textsc{bru}	&		115		&	332 \\
%
\textsc{lga}	&	\textsc{jfk}		&		230		&	37 &
\textsc{jfk}		&	\textsc{cdg}	&		37		&	693 \\
\textsc{jfk}		&	\textsc{lhr}		&		56		&	528 &
\textsc{jfk}		&	\textsc{fra}	&		20		&	412 \\
%
\textsc{ctl}		&	\textsc{lhr}		&		53		&	528 &
\textsc{ctl}		&	\textsc{fra}	&		28		&	412 \\
\textsc{ctl}		&	\textsc{cdg}	&		34		&	593 &
\textsc{atl}		&	\textsc{cdg}	&		19		&	607 \\
\textsc{atl}		&	\textsc{lhr}		&		23		&	466 &
\textsc{atl}		&	\textsc{zrh}	&		18		&	499 \\
%
\textsc{bru}	&	\textsc{cdg}	&		14		&	71 &
\textsc{zrh}	&	\textsc{cdg}	&		335		&	53 \\
\textsc{lhr}	&	\textsc{cdg}		&		211		&	35 &
\textsc{fra}	&	\textsc{cdg}	&		412		&	57 \\
\textsc{mla}	&	\textsc{cdg}	&		111		&	34 &


\end{tabular}
\end{center}
Express a linear program in standard form to solve this problem.
[Extra credit: actually solve the LP and find out how much will it cost me.]


\begin{problem} Andrew's Libraries \end{problem}

\begin{quote}
When a boy in Pittsburgh, striving with all his might to improve his prospects, [Andrew Carnegie]
was permitted with some other youths to borrow books from the library of a gentleman named
Colonel Anderson.  Every Saturday afternoon the good-hearted Colonel was in attendance at his house
to lend any of his four hundred books.  Young Carnegie eagerly looked forward to those Saturday afternoons...The young telegraph messenger resolved in his buoyant enthusiasm that if ever wealth fell to his lot he would use it to establish free libraries, so that poor boys might have opportunities of reading the best books.\hfil [Excerpt from {\em Andrew Carnegie: the man and his work}, Alderson, 1909, p. 156]
\end{quote}

\noindent Suppose it is Andrew's legacy to ensure that every town either has a library or is next to a town that has a library.  Given a map of a country consisting of towns and roads between them, the {\em Library} problem is to decide whether
$k$ libraries can be placed in towns so as to satisfy Andrew's legacy.  
Show that the {\em Library} problem is NP-complete.



\end{document}
