\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 6}}{}{{\sc Course: COMPSCI531D}}
\setft{{\sc Fall 2021}}{{\sc Introduction to Algorithms}}{{\sc Page \thepage}}

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

\noindent\textbf{Due Date: October 28, 11:59pm}

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



\begin{prob}[10pts]
Given points $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$ in the plane, we want to measure how closely the line $y = ax+b$ with $a, b\in \reals$ fits the set of points.
\begin{enumerate}[label=(\alph*)]
	\item{[5pts]} The $L_1$ error of the line $y = ax + b$ is defined as
	follows:
	\[\varepsilon_1(a, b) = \sum_{i=1}^n |y_i-ax_i-b|\]
	Describe a linear program whose solution $(a, b)$ describes the line with minimum $L_1$ error.
	\item {[5pts]}
	The $L_\infty$ error of the line $y = ax + b$ is defined as
	follows:
	\[\varepsilon_\infty(a, b) = \max_{i=1}^n |y_i-ax_i-b|\]Describe a linear program whose solution $(a, b)$ describes the line with minimum $L_\infty$ error.
\end{enumerate}
\end{prob}


\begin{prob}[10pts]
	Recall the LP formulation of the adword problem discussed in class:
	\begin{alignat*}{3}
		& \max & \sum_{\substack{1\le i\le n\\ 1\le j \le m}} b_{ij}x_{ij}& \\
		& \text{subject to} & \sum_{i=1}^n x_{ij}& \le 1 \quad& 1 &\le j \le m\\
		& & \sum_{j=1}^m b_{ij}x_{ij}& \le B_i \quad& 1 &\le i \le n \\
		&& x_{ij}& \ge 0 
	\end{alignat*}
	Write the dual of this linear program. 
	
	\end{prob}

\begin{prob}[10pts]
\begin{enumerate}[label=(\alph*)]
	\item {[5pts]} 
	Consider the maximum weighted matching problem in a weighted bipartite graph $G = (U \cup V, E)$, where $E\subseteq U \times V, w: E\rightarrow \reals_{\ge 0}$. Consider its relaxed LP formulation:
	\begin{alignat*}{3}
		& \max & \sum_{(i,j)\in E} w(i,j)x_{ij} \\
		& \text{subject to} & \sum_{j\in V} x_{ij} &\le 1 \quad& \forall i \in U\\
		& & \sum_{i\in U} x_{ij}& \le 1 \quad&\forall j \in V\\ 
		&& x_{ij}& \ge 0 
	\end{alignat*}
	Show that there is an optimal solution that is integral, i.e., in which each $x_{ij} \in \{0, 1\}$. 
	
	\item{[5pts]} Now dualize the linear program from part (a). What do the dual variables represent? What does the objective function represent?
\end{enumerate}
\end{prob}





\end{document}
