\documentclass[10pt]{article}
\usepackage{epsfig}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{amscd}
\usepackage{amsmath}
\usepackage{xspace}
\usepackage{theorem}
\usepackage{float}
%\usepackage{layout}% if you want to see the layout parameters
% and now use \layout command in the body
% This is the stuff for normal spacing
\makeatletter
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{0.25in}
\setlength{\textheight}{8.25in}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\marginparwidth}{59pt}
\setlength{\parindent}{0pt}
\setlength{\parskip}{5pt plus 1pt}
\setlength{\theorempreskipamount}{5pt plus 1pt}
\setlength{\theorempostskipamount}{0pt}
\setlength{\abovedisplayskip}{8pt plus 3pt minus 6pt}
\setlength{\intextsep}{15pt plus 3pt minus 6pt}
\renewcommand{\section}{\@startsection{section}{1}{0mm}%
{2ex plus -1ex minus -.2ex}%
{1.3ex plus .2ex}%
{\normalfont\Large\bfseries}}%
\renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}%
{1ex plus -1ex minus -.2ex}%
{1ex plus .2ex}%
{\normalfont\large\bfseries}}%
\renewcommand{\subsubsection}{\@startsection{subsubsection}{3}{0mm}%
{1ex plus -1ex minus -.2ex}%
{1ex plus .2ex}%
{\normalfont\normalsize\bfseries}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{0mm}%
{1ex \@plus1ex \@minus.2ex}%
{-1em}%
{\normalfont\normalsize\bfseries}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
{2.0ex \@plus1ex \@minus .2ex}%
{-1em}%
{\normalfont\normalsize\bfseries}}
\makeatother
\newcounter{thelecture}
\newenvironment{proof}{{\bf Proof: }}{\hfill\rule{2mm}{2mm}}
\newenvironment{proofof}[1]{{\bf Proof of #1: }}{\hfill\rule{2mm}{2mm}}
\newenvironment{proofofnobox}[1]{{\bf#1: }}{}
\newenvironment{example}{{\bf Example: }}{\hfill\rule{2mm}{2mm}}
%\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\renewcommand{\thefigure}{\thesection.\arabic{figure}}
\newtheorem{fact}{Fact}
\newtheorem{lemma}[fact]{Lemma}
\newtheorem{theorem}[fact]{Theorem}
\newtheorem{definition}[fact]{Definition}
\newtheorem{corollary}[fact]{Corollary}
\newtheorem{proposition}[fact]{Proposition}
\newtheorem{claim}[fact]{Claim}
\newtheorem{exercise}[fact]{Exercise}
% math notation
\newcommand{\R}{\ensuremath{\mathbb R}}
\newcommand{\Z}{\ensuremath{\mathbb Z}}
\newcommand{\N}{\ensuremath{\mathbb N}}
\newcommand{\B}{\ensuremath{\mathbb B}}
\newcommand{\F}{\ensuremath{\mathcal F}}
\newcommand{\SymGrp}{\ensuremath{\mathfrak S}}
\newcommand{\prob}[1]{\ensuremath{\text{{\bf Pr}$\left[#1\right]$}}}
\newcommand{\expct}[1]{\ensuremath{\text{{\bf E}$\left[#1\right]$}}}
\newcommand{\size}[1]{\ensuremath{\left|#1\right|}}
\newcommand{\ceil}[1]{\ensuremath{\left\lceil#1\right\rceil}}
\newcommand{\floor}[1]{\ensuremath{\left\lfloor#1\right\rfloor}}
\newcommand{\ang}[1]{\ensuremath{\langle{#1}\rangle}}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\polylog}{\operatorname{polylog}}
% anupam's abbreviations
\newcommand{\e}{\epsilon}
\newcommand{\eps}{\epsilon}
\newcommand{\half}{\ensuremath{\frac{1}{2}}}
\newcommand{\junk}[1]{}
\newcommand{\sse}{\subseteq}
\newcommand{\union}{\cup}
\newcommand{\meet}{\wedge}
\newcommand{\dist}[1]{\|{#1}\|_{\text{dist}}}
\newcommand{\hooklongrightarrow}{\lhook\joinrel\longrightarrow}
\newcommand{\embeds}[1]{\;\lhook\joinrel\xrightarrow{#1}\;}
\newcommand{\mnote}[1]{\normalmarginpar \marginpar{\tiny #1}}
\newcommand{\OPT}{\textsf{OPT}}
\newcommand{\That}{\widehat{T}}
\newcommand{\Ghat}{\widehat{G}}
\newcommand{\chat}{\widehat{c}}
\newcommand{\APX}{\ensuremath{\mbox{\tt APX}}}
\newcommand{\IR}{\ensuremath{\mathbb{R}}}
\newcommand{\argmin}{\ensuremath{\mbox{argmin}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Document begins here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\hwheadings}[3]{
{\bf Approximation Algorithms} \hfill {{\bf Take-home Final}}\\
{{\bf Date:} #1} \hfill {{\bf Due:} #2} \\
\rule[0.1in]{\textwidth}{0.025in}
%\thispagestyle{empty}
}
\begin{document}
\hwheadings{Nov 30, 2005}{Dec 12, 2005}
\textbf{Note:} In all these problems: if we ask you to show an
approximation ratio of $\rho$, you should tell us about the best
approximation ratio you did prove, be it better or worse than
$\rho$. Absolutely no discussion or collaboration is allowed between
students when working on the exam. Finally, please refrain from
consulting any external sources (papers, lecture notes, books,
surveys) in attempting to solve these problems.
\begin{enumerate}
\item \textbf{(1,2-TSP)}
Find a polynomial time approximation algorithm with performance
ratio $\frac43$ for the metric TSP problem on a complete graph where
all edge costs are either 1 or 2.
(Hint: Homework 1, Problem 4a is polynomial time solvable.)
\item
\textbf{(Greedy algorithms)} The $k$-cut problem is defined on an
undirected graph with nonnegative capacities on its edges. The goal
is to find a minimum capacity set of edges whose deletion results in
the graph disconnecting into at least $k$ connected components.
Consider the following algorithm for the minimum-$k$-cut problem:
For every connected component of an input graph $G$, compute a
minimum cut. Remove the lightest one. Now repeat and compute minimum
cuts for all connected components. Again remove the lightest one.
Repeat this procedure until there are at least $k$ connected
components. Output the union of the min-cuts that you removed.
Show that this algorithm is a $(2-2/k)$ approximation for the
$k$-cut problem.
\begin{quote}
(Hint: A natural way to try to do this is to "charge" the $k-1$ cuts
found by the algorithm to the $k$ different shores of the optimal
solution as we did for the multiway cut problem early in the course.
However, we do not have any "terminals" in the current problem to
assign identities to these shores easily.
A very useful tool tool to carry out this charging scheme is what is
called a cut-equivalent tree for the given capacitated graph. A
brief description follows.
Let $G = (V,E)$ be a connected undirected graph, and as before, let
every edge $ij \in E$ be assigned a nonnegative capacity $c(ij)$.
The tree we define is on the same set of vertices as $G$. Note that
we do {\em not} require that the edges of $T$ be a subset of the
edges of $G$ -- the tree $T$ is only intended to capture the
structure of minimum cuts in $G$.
A {\bf cut-equivalent tree} (relative to $G$) is defined as a tree
$T$ with $V(T) = V(G)$ with the following property: for every edge
$xy \in E(T)$, the removal of $xy$ from $T$ partitions $V(T) = V(G)$
into two subsets $X \ni x$ and $Y \ni y$; then we require the cut
$\delta(X)$ in $G$ to be a minimum capacity cut separating $x$ and
$y$.
You may assume that you have a polynomial time algorithm available
to build a cut-equivalent tree on the given capacitated graph to
solve this problem.)
\end{quote}
\item
\textbf{(A Shifting Analysis)} This is not exactly something we did
in class but it quite commonly used in geometric settings to design
polynomial time approximation schemes. Suppose we are given $n$
points $p_1, \ldots p_n$ in an area $I \subseteq \IR^2$. We now want
to cover all of these points with as few disks of diameter $D>0$ as
possible. In this question, you will develop a polynomial-time
approximation scheme for this problem.
\begin{itemize}
\item[(a)] Suppose at first, that $I$ is a square of side-lengths
$l\cdot D$ for some constant $l>0$. Give a polynomial-time algorithm
that
solves these instances exactly.\\
{\bf Hint:} Show first, that you need $O(l^2)$ disks to cover $I$.
Then, prove that you need to consider only $O(n^2)$ potential
positions for each disk.
% You can assume that any disk in \OPT's cover has
% at least two input-points on its boundary (why?).
% This should help
% you to bound the time needed to perform an exhaustive search
% over all possible ways to cover $I$.
\item[(b)] In the following assume that $I$ is an arbitrary convex
subset of $\IR^2$. Look at the following natural shifting strategy:
Take $I$ and partition it along the $x$-axis into strips of width
$l\cdot D$. Let this partition be $\Pi_1= \{S^1_1, \ldots, S^1_k\}$.
We can get another partition by {\em shifting} each of the $S^1_i$'s
by a distance $D$ to the right ($S^1_k$ is shifted cyclically -- the
shifted set $S^2_k$ covers the leftmost strip of width $D$ that was
previously covered by $S^1_1$). Call this partition $\Pi_2$. Notice,
that we can get $l$ partitions $\Pi_1, \ldots, \Pi_l$ using shifts in
this way and that $\Pi_{l+1}=\Pi_1$. In the following, let
$$ \Pi_i = \{S^i_{1}, \ldots, S^i_k\}. $$
Now, suppose that you are given a $\rho$-approximation algorithm $A$
that deals with instances where the length of the area $I$ is bounded
by $l\cdot D$ along one dimension. For each of the partitions
$\Pi_i$, compute a solution as follows: use $A$ to compute a feasible
disk-covers $C^i_1, \ldots, C^i_k$ for each of the strips $S^i_1,
\ldots, S^i_k$. Then let $\APX^i= C^i_1 \cup \ldots \cup C^i_k$.
Return
$$
\APX = \argmin_{1 \leq i \leq l} |\APX^i|. $$
Show that $|\APX|
\leq \rho\cdot (1+1/l)|\OPT|$.
\item[(c)] How do (a) and (b) lead to a PTAS for the euclidian disk
cover problem?
\end{itemize}
\item \textbf{(Densest Subgraph)} Given an undirected graph $G = (V,E)$,
the density of a subset $S$ is defined to be
\begin{gather}
\rho(S) = \frac{|E(S,S)|}{|S|};
\end{gather}
i.e., the number of edges with both endpoints in $S$, divided by the
number of vertices in $S$. The goal of this problem is to find the
subset $S$ which maximizes $\rho(S)$, the max being taken over all
subsets of $V$.
\begin{enumerate}
\item Consider the following LP relaxation for the problem: have a
variable $x_{ij}$ for each edge $\{i,j\}$, and variable $y_i$ for
each vertex $i \in V$. The goal is to maximize $\sum_{ij} x_{ij}$
subject to the constraints:
\begin{align*}
x_{ij} &\leq \min\{ y_i, y_j \} \qquad\qquad \forall \{i,j\} \in E\\
\textstyle\sum_{i \in V} y_i &\leq 1.
\end{align*}
Is this a \emph{linear} program? If not, write an equivalent LP for
the problem. Show that this is a valid relaxation for the Densest
Subgraph problem.
\item Give the best (upper and lower) bounds you can on the
integrality gap of this LP relaxation.
\end{enumerate}
\item \textbf{(Local Ratio is Primal Dual)} Recall from the lectures on
the Local Ratio method that the process of ``stripping off'' one edge
at a time to build a decomposition yields a 2-approximation algorithm
for the vertex cover problem (cf. Lecture 9 notes).
Such local ratio decomposition steps naturally lead to an idea for
primal-dual algorithms, esp. in terms of the dual update step. In
particular, this naturally defines a primal-dual algorithm for the
vertex cover problem where at every step, we pick any (as yet
uncovered) edge and raise its dual value until the dual constraint
corresponding to either endpoint becomes tight. Use this ideas to
write down a primal dual algorithm for vertex cover and show how it's
performance ratio is 2.
Then, do the same for the directed spanning tree problem from Homework
4, Problem 1. Be very careful here: First write the ILP formulation
for the directed spanning tree problem with an exponential number of
constraints (similar to the one for undirected Steiner trees that we
wrote in class). Then show how the local decomposition steps in the
algorithm can be used to define an appropriate dual update step.
Finally, show that this approximation ratio has performance ratio 1
(i.e., it is an exact primal-dual algorithm for directed spanning
trees)!
\iffalse
\textbf{(Greedy independent sets)}
Show that the greedy algorithm for maximum independent set has
performance ratio equal to the average degree of the input graph.
\fi
\item \textbf{(Unique Set Cover)} Consider the following problem: we are
given a universe $U$ with $n$ elements, and a family of sets $\F =
\{S_1, S_2, \ldots, S_m\}$. The goal is to pick some subfamily $\F'$
of $K$ sets to maximize the number of elements that are covered by
\emph{exactly one} set in this subfamily. (I.e., they are covered
\emph{uniquely}.)
\begin{enumerate}
\item Suppose we are working in a simple case when all the elements of
$U$ are contained in exactly $d$ of the sets in $\F$. Choose a
probability $p = p(d)$ such that adding each set from $\F$ to our
family $\F'$ with probability $p$ will result in $\Omega(1)$ of the
elements of $U$ being covered uniquely.
How does your analysis change if each element $u$ is contained in
$d_u$ of the sets, where $\forall u\in U, d_u \in [d, 2d]$ for some
universal quantity $d$?
\item By classifying the elements into suitable groups and using the
above algorithm, obtain an $O(\log D)$ approximation algorithm for
the problem, where $D$ is the maximum number of sets in which any
element in $U$ is contained. Show that this implies an $O(\log m)$
approximation algorithm for the problem.
\item (Not very difficult, but not for credit) Can you extend this
idea to get an $O(\log n)$ approximation algorithm for the problem?
\end{enumerate}
\end{enumerate}
\end{document}