\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}