\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,graphicx,xcolor}
\newcommand{\eps}{\varepsilon}
\newcommand{\fig}[2]{\begin{figure}[h]\begin{center}%
\includegraphics[scale=#2]{#1.pdf}\end{center}%
\end{figure}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2022)\\
{\Large Homework 10} (due April 21 Thursday at 10am)
\end{center}
\medskip
\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 10.1:]
Consider the following geometric matching problem: Given a set
$A$ of $n$ points and a set $B$ of $n$ points in 2D, find a set of $n$ pairs
$S=\{(a_1,b_1),\ldots, (a_n,b_n)\}$, with $\{a_1,\ldots, a_n\}=A$ and
$\{b_1,\ldots, b_n\}=B$, minimizing $f(S)=\sum_{i=1}^n d(a_i,b_i)$.
Here, $d(a_i,b_i)$ denotes the Euclidean distance between $a_i$
and $b_i$ (which you may assume can be computed in $O(1)$ time).
Assume that all points in $A$ have $y$-coordinate equal to 0
and all points in $B$ have $y$-coordinate equal to 1.
(Thus, all points lie on two horizontal lines.) The points are not sorted.
See the example below, which shows a solution that is definitely not optimal.
\fig{hw10fig1}{0.8}
\vspace{-3ex}
\begin{enumerate}
\item[(a)] (20 pts)\ \ Consider the following greedy strategy:
pick a pair $(a,b)\in A\times B$ minimizing $d(a,b)$;
then remove $a$ from $A$ and $b$ from $B$, and repeat.
Give a counterexample showing that this algorithm does not always give
an optimal solution.
\smallskip
\item[(b)] (40 pts)\ \ Let $a$ be the point in $A$ with the smallest $x$-coordinate.
Let $b$ be the point in $B$ with the smallest $x$-coordinate.
Consider a solution $S$ in which $a$ is paired with some point $b'$ with $b'\neq b$, and $b$
is paired with some point $a'$ with $a'\neq a$.
Prove that the solution $S$ can be modified to obtain a new solution $S'$ with $f(S')