\documentclass[11pt]{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{\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}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Document begins here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\hwheadings}[3]{
{\bf Approximation Algorithms} \hfill {{\bf Homework #1}}\\
{{\bf Date:} #2} \hfill {{\bf Due:} #3} \\
\rule[0.1in]{\textwidth}{0.025in}
%\thispagestyle{empty}
}

\begin{document}

\hwheadings{1}{Sept 14, 2005}{Sept 21, 2005}

\begin{enumerate}
\item {\bf $K$-center:} 
Consider an undirected {\em complete} graph $G = (V,E)$ with 
nonnegative {\em metric} distances $d$ on the edges; i.e., 
$d_{ij} + d_{jk} \geq d_{ik}$ for all $i, j, k \in V$.
Given $G$ and a positive integer $K$, the $K$-center problem 
asks for a subset $C \subseteq V$ of vertices of size $|C| = K$ 
that minimizes
\begin{gather} 
\max_{v \in V} \, d(v, C).
\end{gather} 
Let $D^*$ be this minimum value. (Note here that $d(v, C) = \min_{x \in C} 
d(v,x)$ is the natural extension of the distance function to sets, namely, 
it is the distance of vertex $v$ to the closest node in $C$.)

Before you begin, convince yourself that this problem is NP-hard. (You
don't have to write this down.) Our goal is to develop an approximation 
algorithm for $D^*$.

\begin{enumerate}
\item A natural {\em greedy} 2-approximation algorithm for this
problem first assumes that we have the right guess for $D^*$. it
starts with all nodes being {\em unmarked}, iteratively chooses 
some unmarked node as a center, marks all the nodes within a distance 
$2D^*$ of this chosen node as covered, and continues the process with 
the remaining unmarked nodes until all nodes are marked. Clearly, each
node is within a distance $2D^*$ of some chosen node at the end of the 
algorithm: to complete the argument, show that we cannot have chosen 
more than $K$ centers before all nodes are marked.

\item Given an instance of the $K$-center problem, show that $D^*$ can 
only take one of $n \choose 2$ values (which depend on the given instance,
of course.) In particular, this will give a method to enumerate set of
$O(n^2)$ values for any given instance, one of which must be $D^*$. 
How can this allow you to remove the assumption that we had the right
guess for $D^*$?

\item Find an example (actually even better, an infinite family of
examples parameterized by size) that demonstrates that the above
greedy algorithm will produce a solution of value $2D^*$ and no
better on the example.

\end{enumerate}

\item {\bf $K$-dispersion:} Given an undirected complete graph $G = (V,E)$ 
with nonnegative {\em metric} distances $d$ on the edges and a given
positive integer $K$, the $K$-dispersion problem asks for a subset $S
\subseteq V$ of vertices of size $k$ (i.e., $|S| = k$) that are as
far apart from each other as possible. Namely, we are trying to {\em
maximize}
\begin{gather}
 \min_{s, s' \in S} d(s,s')
\end{gather}
Let this quantity be denoted by $F^*$. A typical application of this 
problem is to locate harmful goods (like nuclear facilities, waste 
dumps etc.) far apart to minimize collective harm that might result 
from interaction.

Consider the following greedy algorithm: start with $S$ being an 
arbitrary node from $V$, and repeatedly add a node furthest from the 
nodes currently in $S$, until you have a total of $k$ nodes. Show that
this is a $2$-approximation algorithm for $F^*$, and show examples to 
show that your algorithm has a performance guarantee no better than $2$.

To strengthen the last part on the limits to the performance of the 
greedy algorithm, we can try to prove a inapproximability result as
well. Show that, unless P = NP, there is no $1.9999$-approximation 
algorithm for $K$-dispersion. 

\item Prove the following \emph{tree-pairing lemma} analogous to the 
\emph{tour-pairing lemma} given in Lecture:

\begin{lemma}[Tree-Pairing Lemma] Given an undirected tree $T = (V, E)$ and a
subset $M \subseteq V$ of even cardinality, find a pairing (perfect
matching) of the nodes in $M$ such that the paths in $T$ between the
matched pairs are edge-disjoint.
\end{lemma}

\item Classify the following problems into P or NP. Provide a brief
explanation with each.

\begin{enumerate}
\item Given an undirected graph $G = (V,E)$ with nonnegative costs $c$ 
on the edges, a \emph{target degree} $d_v$ for each node  $v \in V$, 
find a subgraph (subset of edges) of minimum total cost whose degree 
at node $v$ is $d_v$.

\item Given an undirected graph $G = (V,E)$ with nonnegative  costs 
$c$ on the edges, a \emph{degree lower bound} $\ell_v$ for each node 
$v \in V$, find a subgraph (subset of edges) of minimum total cost 
whose degree at node $v$ is at least $\ell_v$.

\item Given an undirected graph $G = (V,E)$ with nonnegative  costs 
$c$ on the edges, a \emph{degree upper bound} $u_v$ for each node 
$v \in V$, find a subgraph (subset of edges) of minimum total cost 
whose degree at node $v$ is at most $u_v$.

\item Given an undirected graph $G = (V,E)$ with nonnegative costs 
$c$ on the edges, and a vertex $v_0 \in V$, find a walk (i.e., a sequence 
of consecutive edges) of minimum total cost such that the walk starts 
and ends at $v_0$, and every edge of the graph appears at least once 
in the walk.

\end{enumerate}

\end{enumerate}

\end{document}