\documentclass[11pt]{article}\pagestyle{empty}
\usepackage{amsmath,amssymb,amsthm,color,graphicx}
\usepackage{euscript}
\usepackage{mathpazo}

\usepackage[top=1.5in,bottom=1.5in,left=1.25in,right=1.25in]{geometry}
%improve trypography

\usepackage{microtype}
\usepackage{fixltx2e}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{tikz}
\usepackage{enumitem}
\usepackage{mathtools}

{\catcode`\@=11
\gdef\setft#1#2#3{%
\def\@oddfoot{%
{\setbox0=\hbox{#1}%
\setbox1=\hbox{#3}%
\ifdim\wd0>\wd1%
\dimen0=\wd0%
\box0\hfil#2\hfil\hbox to\dimen0{\hfil\hfil\box1}%
\else \dimen0=\wd1%
\hbox to\dimen0{\box0\hfil}\hfil#2\hfil\box1\fi%
}}}}

{\catcode`\@=11
\gdef\sethd#1#2#3{%
\def\@oddhead{\vbox{\hbox to\hsize{{#1}\hfil{#2}\hfil{#3}}%
\vspace{0.06in}%
\hbox to \hsize{\hrulefill}\vspace*{-0.09in}}}
\def\@evenhead{\@oddhead}
	}
}

\def\reals{\mathbb{R}}
\def\sphere{\mathbb{S}}
\def\xx{\mathbf{x}}
\def\norm#1{\Vert #1 \Vert}
\def\hint#1{(\textbf{Hint:} #1)}
\def\floor#1{\lfloor #1 \rfloor}
\def\ceiling#1{\lceil #1 \rceil}

\DeclareMathOperator*{\argmin}{arg\,min}



\marginparsep=1pt
\oddsidemargin=0.25in
%
%%%%%% A few macros %%%%%%%%%%%%%%%%
\newtheorem{probm}{Problem}
\newenvironment{prob}{\noindent{\bf Problem \addtocounter{probm}{1}
\hspace{-1mm}\theprobm:\hspace{2mm}}}{\vspace{2mm}}

\def\hint#1{\noindent ({\bf Hint:} {\it #1})}
\def\eps{\varepsilon}
\def\conv{\mathop{\mathrm{conv}}}

\parskip=2mm
\sethd{{\sc Assignment 7}}{}{{\sc Course: COMPSCI531D}}
\setft{{\sc Fall 2021}}{{\sc Introduction to Algorithms}}{{\sc Page \thepage}}

\begin{document}
\vspace*{2mm}

\noindent\textbf{Due Date: November 4, 11:59pm}

% \noindent In all problems, prove the correctness of your algorithm and analyze its running time.



\begin{prob}[10pts]
Let $G=(V,E)$ be a graph with a weight function $w: E\rightarrow \reals_{\ge 0}$. Consider the following linear program for minimum spanning trees in $G$:
\begin{alignat*}{3}
	& \min & \sum_{e\in E} w(e)\cdot x_e& \\
	& \text{subject to} & \sum_{e\in E(S,\overline S)}^n x_{e}& \ge 1 \quad& \text{for all } S\subseteq V, \overline S = V-S\\
	&& x_{e} &\ge 0
\end{alignat*}
\end{prob}\\
Given any $x \in \reals^E$, a separation oracle determines whether $x$ is a feasible solution to the linear program in polynomial time. If $x$ is infeasible, it also returns a constraint not satisfied by $x$. Design a separation oracle for the exponential set of constraints, and analyze the running time.

\begin{prob}[10pts]
Solve the following linear proram using the simplex method, with the slack variables as the initial basis. In the first step, $x_1$ should be the variable entering the basis. 
\begin{alignat*}{3}
	& \max & -x_1 + x_2 \\
	& \text{subject to} \quad& x_1-x_2 &\le 2 \\
	&& 2x_1-x_2 &\le 6\\
	&& -x_1+x_2 &\le 4\\
	&& x_1 &\le 6 \\
	&& x_2 &\le 8 \\
	&& x_1, x_2 &\ge 0
\end{alignat*}
Draw the feasible region in 2D. Write the sequence of basis. Show the simplex tableau for each basis, and draw the sequence of vertices visited by the algorithm. 
\end{prob}






\end{document}
