\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}}
\newlength{\mylength}
\newcommand{\scratch}[1]{\makebox[0in][l]{#1}\settowidth{\mylength}{#1}{\color{red}\rule[.6ex]{\mylength}{1pt}}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 10} (due Apr 18 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 10.1:]
Consider the following problem: given a set $S$ of $n$ distinct
positive integers and a number $L$, we want to form the largest
number of disjoint pairs in $S$, such that the sum of each pair is at most $L$.
For example, for $S=\{1,3,4,5,8\}$ and $L=10$, an optimal solution
has 2 pairs (e.g., one optimal solution is $\{1,8\}$ and $\{4,5\}$, but there are a number of other solutions that are also optimal).
Consider the following greedy strategy:
\begin{quote}
\begin{tabbing}
for \=\kill
repeat \{\\
\> find a pair $\{a,b\}\subseteq S$ with $a+b\le L$ maximizing $a+b$\\
\> if no such pair exists then stop\\
\> else output the pair $\{a,b\}$, and remove $a$ and $b$ from $S$\\
\}
\end{tabbing}
\end{quote}
\begin{enumerate}
\item[(a)] (85 pts) Prove that this algorithm always correctly finds
an optimal solution.
Like various greedy correctness proofs from class,
you should use an ``exchange'' argument: let $\{a,b\}\subseteq S$ with $a+b\in L$ maximizing $a+b$; suppose $P^*$ is an optimal solution, and
suppose $\{a,b\}$ is not in $P^*$; show how to modify $P^*$ to get a different feasible solution that is
just as good and that uses $\{a,b\}$\ldots
\smallskip
\item[(b)] (15 pts) Consider a variant of the problem, where we want to
find the largest number of disjoint triples, such that the sum of each triple is at most $L$.
Show that
the same greedy strategy (where now we find a triple $\{a,b,c\}\subseteq S$
with $a+b+c\le L$ maximizing $a+b+c$ at each iteration) does not always
correctly find an optimal solution. You should give
a counterexample with $n=9$.
\end{enumerate}
\bigskip
\item[Problem 10.2:]
Consider the following search problem:
\begin{quote}
{\sc Max-Rectangle-Coverage}:\\[2pt]
\emph{Input:} a set $R$ of $m$ rectangles, a set $P$ of $n$ points in 2D, and a number $k\le m$.\\[2pt]
\emph{Output:} Find a subset $Q\subseteq R$ of $k$ rectangles, while maximizing the number of points of $P$
covered by $Q$.
\end{quote}
(Here, a point $p\in P$ is \emph{covered} by $Q$ iff $p$ is contained in $r$ for some rectangle $r\in Q$.)
Consider the following decision problem:
\begin{quote}
{\sc Max-Rectangle-Coverage-Decision}:\\[2pt]
\emph{Input:} a set $R$ of $m$ rectangles, a set $P$ of $n$ points in 2D, and numbers $k\le m$ and $\ell\le n$.\\[2pt]
\emph{Output:} True iff there exists a subset $Q\subseteq R$ of $k$ rectangles, such that the number of points of $P$
covered by $Q$ is at least $\ell$.
\end{quote}
Prove that {\sc Max-Rectangle-Coverage} has a polynomial-time algorithm iff {\sc Max-Rectangle-Coverage-Decision}
has a polynomial-time algorithm.
(Note: one direction should be easy; for the other direction, see lab 12b for examples of this type of question.)
\end{description}
\end{document}