\documentclass[11pt]{article}
	\usepackage[margin=1in]{geometry}
	\usepackage{amsfonts, amsmath, amssymb, amsthm}
	\usepackage{microtype}
	\usepackage{nicefrac}
	\usepackage[small]{complexity}

	\usepackage[colorlinks=true]{hyperref}
	\hypersetup{
		linkcolor=[rgb]{0.5, 0.2, 0.2},
		citecolor=[rgb]{0.2, 0.5, 0.2},
		urlcolor =[rgb]{0.2, 0.2, 0.5}
	}

	% complexity, needs to be after hyperref to work
		\renewcommand{\S}{\defaultS}
		\renewcommand{\L}{\ComplexityFont{L}}
		\newcommand{\ETIME}{\ComplexityFont{E}}

	\newcommand{\thecourse}{\errmessage{Course is undefined}}
	\newcommand{\handout}[5]{
		%\renewcommand{\thepage}{#1-\arabic{page}}
		\noindent%
		\begin{center}%
			\framebox{%
				\vbox{%
					\vspace{1mm}%
					\hbox to 5.78in {
						{\bf \thecourse}%
						\hfill%
						\smash{\parbox[t]{3in}{\raggedleft #2}}%
					}%
					\vspace{\baselineskip}%
					\hbox to 5.78in { {\Large \hfill #5  \hfill} }%
					\vspace{\baselineskip}%
					\hbox to 5.78in {%
						\smash{\parbox[b]{2.5in}{\raggedright #3}}%
						\hfill
						\smash{\parbox[b]{3in}{\raggedleft #4}}%
						}%
				}%
			}%
		\end{center}%
		\vspace*{4mm}%
	}%

	% \setlength\parindent{0pt}

	% https://tex.stackexchange.com/questions/21004/add-asterisk-after-labels-in-enumerate
	\newenvironment{starnumerate}{\enumerate\setupstarnumerate}{\endenumerate}
	\newif\ifstaritem
	\newcommand{\setupstarnumerate}{%
		\global\staritemfalse
		\let\origmakelabel\makelabel
		\def\staritem##1{\global\staritemtrue\def\mesymbol{##1}\item}%
		\def\makelabel##1{%
		\origmakelabel{##1\ifstaritem\rlap{\mesymbol}\fi\enspace}%
		\global\staritemfalse}%
	}

	% math
	\newcommand{\N}{\mathbb{N}}
	\newcommand{\F}{\mathbb{F}}
	\newcommand{\bits}{\ensuremath{\{0,1\}}}
	\newcommand{\la}{\langle}
	\newcommand{\ra}{\rangle}
	\newcommand{\rX}{\mathsf{X}}
	\newcommand{\rY}{\mathsf{Y}}
	\newcommand{\rZ}{\mathsf{Z}}
	\newcommand{\e}{\mathrm{e}}
	\renewcommand{\vec}[1]{\overline{#1}}
	\newcommand{\floor}[1]{\lfloor #1 \rfloor}
	\newcommand{\ceil}[1]{\lceil #1 \rceil}
	\newcommand{\eps}{\epsilon}
	\DeclareMathOperator{\Var}{Var}

	\renewcommand{\E}{\mathbb{E}}

	%	open/closed intervals
	%       [
	\newcommand{\ocint}[2]{\ensuremath{(#1,#2]}}%)
	\newcommand{\icint}[1]{\ocint{\infty}{#1}}
	%       (
	\newcommand{\coint}[2]{\ensuremath{[#1,#2)}}%]
	\newcommand{\ciint}[1]{\coint{#1}{\infty}}
	\newcommand{\ccint}[2]{\ensuremath{[#1,#2]}}%)
	\newcommand{\ooint}[2]{\ensuremath{(#1,#2)}}%)

	% copied from 2018-01_cs473-algorithms.lectures.zip/prefix.tex
	\newcommand{\fcode}[1]
		{
			\smallskip
			\centerline{
				\fbox{
					\begin{minipage}{0.95\linewidth}
						\code{#1}
					\end{minipage}
				}
			}
			\smallskip
		}
	\newcommand{\innercode}[1]
		{
			\begin{tabbing}
				----\=----\=----\=----\=----\=----\=----\kill
				#1
			\end{tabbing}
		}
	\newcommand{\code}[1]
		{
			\footnotesize
			\tt
			\begin{center}
				\innercode{#1}
			\end{center}
		}

	\newcommand{\cH}{\mathcal{H}}
	\newcommand{\Z}{\mathbb{Z}}

	% 2024-01_cs473-algorithms/pset8

	\usepackage{mathtools}
	\newcommand{\iP}{\reflectbox{\rotatebox[origin=c]{180}{$\Pi$}}}

\begin{document}

\renewcommand{\thecourse}{cs473 Algorithms}
\handout{0}%
	{}%
	{Prof.\ Michael A. Forbes}%
	{Due: \textit{Fri., 2026-04-10 17:00}}%
	{Problem Set \#8}

All problems are of equal value.

\begin{enumerate}

	\item Consider the linear program $\Pi$ defined by
		\[
				\begin{aligned}
					&&\max 2x+y	&\\
					\text{st} &&x+2y	&\le12,\\
					&&-x+3y	&\le 9,\\
					&&2x-3y	&\le8,\\
					&&x,y	&\ge0
				\end{aligned}
		\]
		\begin{enumerate}
			\item Define a \emph{vertex} to be a point $(x,y)$ that is both feasible, and makes two of the linear \emph{in}equalities into \emph{equalities}.  For example, $(0,0)$ is a vertex because it is feasible and meets the constraints $x\ge 0$ and $y\ge 0$ with equality.

				Give a list of all vertices of $\Pi$, with a proof of correctness.
			\item Draw $P$ as a subset of $\mathbb{R}^2$.
			\item Derive the dual $\iP$ to $\Pi$.
			\item As the dual $\iP$ is in three variables, a vertex of this system of constraints now asks for \emph{three} of the inequalities to be met.  Give a list of all vertices, with a proof of correctness.
			\item Solve $\Pi$ by providing a primal feasible point and a dual feasible point witnessing that $|\Pi|=|\iP|$.
		\end{enumerate}

	\item  Minimum-cost circulation.  Erickson \href{https://jeffe.cs.illinois.edu/teaching/algorithms/notes/H-lp.pdf}{Chapter H}, Problem \#3.

	\item  Large squares and rectangles.  Erickson \href{https://jeffe.cs.illinois.edu/teaching/algorithms/notes/H-lp.pdf}{Chapter H}, Problem \#4 (a),(b),(d) \emph{only}.

\end{enumerate}

\end{document}
