\documentclass[12pt]{article}
\usepackage{fullpage}
%\usepackage{times}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{latexsym}
\newcommand{\myparskip}{6pt}
\parskip \myparskip
\newtheorem{lemma}{Lemma}[section]
\newtheorem{theorem}[lemma]{Theorem}
\newtheorem{assumption}[lemma]{Assumption}
\newtheorem{definition}[lemma]{Definition}
\newtheorem{corollary}[lemma]{Corollary}
\newtheorem{prop}[lemma]{Proposition}
\newtheorem{claim}[lemma]{Claim}
\newtheorem{remark}[lemma]{Remark}
\newtheorem{prob}{Problem}
\newenvironment{myprob}{\begin{prob} \em}{\end{prob}}
\newcommand{\opt}{\mbox{\sc opt}}
\newcommand{\eps}{\epsilon}
\begin{document}
\setlength{\fboxrule}{.5mm}\setlength{\fboxsep}{1.2mm}
\newlength{\boxlength}\setlength{\boxlength}{\textwidth}
\addtolength{\boxlength}{-4mm}
%\begin{center}\framebox{\parbox{\boxlength}{%\bf
\begin{center}
{\bf Spring 2016, CS 583: Approximation Algorithms\\~\\
Homework 3}\\
Due: 3/18/2016
\end{center}
%}}\end{center}
\vspace{5mm}
\noindent {\bf Instructions and Policy:} Each student should write up
their own solutions independently. You need to indicate the names of
the people you discussed a problem with; ideally you should discuss
with no more than two other people.
\noindent
Read through all the problems
and think about them and how they relate to what we covered in the
lectures. Solve as many problems as you can. Please submit your
solutions to at least 4 problems.
\noindent
Please write clearly and concisely - clarity and brevity will be
rewarded. Refer to known facts as necessary. Your job is to convince
me that you know the solution, as quickly as possible.
\begin{myprob}
In the Rectangle Independent Set problem (RIS) we are given a
collection of $n$ axis-parallel rectangles $\mathcal{R} =
\{R_1,\ldots,R_n\}$ in the plane and the goal is to find a maximum
cardinality subset of the rectangles that do not overlap. In this
problem you will derive an $\Omega(1/\log n)$-approximation. Given a
horizontal line $L$ let $\mathcal{R}_a$ be the set of rectangles in
$\mathcal{R}$ that lie above $L$, and let $\mathcal{R}_b$ be the set
of rectangles that lie below $L$, and let $\mathcal{R}_c$ be the set
of rectangles that intersect $L$.
\begin{itemize}
\item Describe a polynomial-time algorithm that finds
an optimum solution for rectangles in $\mathcal{R}_c$.
\item Prove that, given $\mathcal{R}$, there is a line $L$ that can
be found in polynomial-time such that $|\mathcal{R}_a|$ and
$|\mathcal{R}_b|$ are both at most $\lceil n/2 \rceil$.
\item Use the above two parts to design a divide and conquer style
algorithm that achieves the desired $\Omega(1/\log n)$-approximation.
\item Does the algorithm extend to the weighted case?
\end{itemize}
\end{myprob}
\begin{myprob}
Problem 2.1 from Williamson-Shmoys book.
\end{myprob}
\begin{myprob}
Problem 2.10 from Williamson-Shmoys book.
\end{myprob}
\begin{myprob}
For the same problem as in the preceding one consider a local-search
algorithm that start with an arbitrary set $S \subseteq E$ of $k$
elements and does a swap if it improves the value. Prove that this
gives a $1/2$-approximation. {\em Hint: Set up an (arbitrary) matching between a
local optimum $S$ and an optimum solution $S^*$ and consider the
swaps corresponding to this matching.}
\end{myprob}
\begin{myprob}
Problem 9.2 from Shmoys-Williamson book. However, there is a slight typo
in the data given for the problem. Assume, that for all facilities, the
opening cost is $2$. The distances $c_{ij}$ remain as given in the problem.
\end{myprob}
\begin{myprob}
Let $G=(V,A)$ be a directed graph with arc weights $c: A\rightarrow
{\cal R}^+$. Define the density of a directed cycle $C$ as $\sum_{a
\in C} c(a) / |V(C)|$ where $V(C)$ is set of vertices in $C$.
\begin{enumerate}
\item A cycle with the minimum density is called a minimum mean
cycle and such a cycle can be computed in polynomial time. How?
\emph{Hint:} Given density $\lambda$, give a polynomial-time
algorithm to test if $G$ contains a cycle of density $<
\lambda$. Now use binary search.
\item Consider the following algorithm for ATSP. Given $G$ (with $c$
satisfying asymmetric triangle inequality), compute a minimum mean
cycle $C$. Pick an arbitrary vertex $v$ from $C$ and recurse on
the graph $G'= G[V - C \cup \{v\}]$. A solution to the problem on
$G$ can be computed by patching $C$ with a tour in the graph $G'$.
Prove that the approximation ratio for this heuristic is at most
$2H_n$ where $H_n = 1+1/2 + \ldots + 1/n$ is the $n$th harmonic
number.
\end{enumerate}
\end{myprob}
\begin{myprob}
For Metric-TSP consider the nearest neighbour heuristic discussed in
class. Prove that the heuristic yields an $O(\log n)$ approximation.
(Hint: use the basic idea in the online greedy algorithm for the
Steiner tree problem from Lecture 1 (Spring 2011)).
{\bf Extra Credit:} Give an example to show
that there is no constant $c$ such that the heuristic is a
$c$-approximation algorithm.
\end{myprob}
\end{document}