\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{\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 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{3}{Sept 28, 2005}{Oct 5, 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$.
\begin{enumerate}
\item \textbf{(K-Center Problem Revisited)} Recall the K-center problem:
We are given 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). \label{eq1}
\end{gather}
Let $D^*$ be this minimum value when $|C| = K$.
Now, we consider a variant: In this, we insist on a solution such that
the distance from every node to its closest center is at most some
specified distance $D^*$, and want minimize the number of centers $K'$
to locate in order to achieve this. (I.e., to defeat the hardness of
the problem, instead of relaxing the distance guarantee, we are
instead allowing ourselves to place more centers.)
Design an algorithm for this problem that places a set of centers $C$
with $|C| = O(K \log |V|)$, and ensures that~(\ref{eq1}) is at most
$D^*$.
\item \textbf{(Max Leaf Spanning Tree Revisited)} The \emph{locality gap}
of an algorithm for this problem is the largest number $\alpha \geq 1$ for
which you can show a LOT $T$ such that $\ell(T) \leq \ell(T^*)/\alpha$,
where $T^*$ is a max-leaf spanning tree.
The algorithm in class showed that $\alpha$ can never be more than $10$.
By exhibiting a suitable family of examples, give the best lower bound
you can for the locality gap of the algorithm given in class.
\item \textbf{(Multiway Cut Revisited)} We can look at \textsc{Multiway
Cut} as a coloring problem: color each node in $V$ with one of $k$
colors such that the terminal $s_i$ is colored with color $i$, so as
to minimize the number of bichromatic edges. (Make sure you believe
this!)
Consider an extension of the problem: here each vertex $v \in V$ has
an associated coloring cost function $C_v: [k] \to \R_{\geq 0}$ such
that the cost of coloring $v$ with color $i$ is $C_v(i)$. Now we want
find a coloring $f: V \to [k]$ so as to minimize the total cost
\begin{gather}
\Phi(f) = \sum_{v \in V} C_v(f(v)) + \text{ number of bichromatic
edges in $f$ }.
\end{gather}
Note that if we set $C_{s_j}(i)$ to be $0$ if $i = j$ and $\infty$
otherwise, and for each non-terminal node $v$, we set $C_v(i) = 0$ for
all colors $i$, then we get back the \textsc{Multiway Cut} problem.
\begin{enumerate}
\item Our local search algorithm will make moves of the following
form: if we are at coloring $f$, pick a color $i$ and try to find
the \emph{best} coloring $f'$ obtained from $f$ by recoloring some
of the vertices by the color $i$. I.e., $f'$ satisfies the property
that either $f'(v) = i$ or $f'(v) = f(v)$, and it is the one with
the least cost. Call such a best coloring an \emph{$i$-move}. (In
case of ties, choose one arbitrarily.) \emph{Note that we have not shown
how to find such an $i$-move; we will discuss this issue later.}
Show that if $f$ is a local optimum with respect to these moves,
(i.e., none of the $k$ potential $i$-moves results in the cost
strictly decreasing), then $\Phi(f) \leq 2 \Phi(\OPT)$. As usual,
$\OPT$ is the optimal coloring.
\item Since it may take a long time to reach a local minimum, we can
change the algorithm to make a move from $f$ to $f'$ as long as it
decreases the cost by at most $\Phi(f) \times (\eps/k)$. Show that
if we start from a coloring $f_0$, then the algorithm takes at most
\begin{gather}
O\bigg(\frac{\log (\frac{\Phi(f_0)}{\Phi(\OPT)})}{- \log (1 -
\eps/k)} \bigg)
\label{BVZ-rounds}
\end{gather}
local improvement steps to reach a solution of cost $2(1+\eps)
\Phi(\OPT)$.
\item Note that the number of steps in the above solution is not
\emph{strongly polynomial}: if the coloring costs $C_v(\cdot)$ are
very large, the number of rounds may be very large (albeit
polynomial in the representation of the instance). One way to fix
this is to choose the start state $f_0$ carefully. Can you show a
choice of $f_0$ so that~(\ref{BVZ-rounds}) is at most $\poly(n, k,
\eps)$?
What about the case when $k \gg n$? Can you change the algorithm so
that the number of steps to reach a near-local-optimum is at most
$\poly(n, \eps)$?
\item Suppose you now wanted to make smaller local-search moves of the
form: pick a vertex $v$ and a color $i$, and paint $v$ with color
$i$ if the resulting $\Phi(f)$ decreases. (These moves are called
the \emph{Glauber dynamics}.) Note that the new algorithm makes much
smaller moves than the one above, and hence may take more time to
reach a local optimum.
All local minima of this new process are also $2$-approximate: give
a proof or a counterexample.
\end{enumerate}
\textbf{Remark: } We did not address the question: given a color $i$
and a coloring $f$, how can we find the best $i$-move? Despite the
fact that there may be $\Omega(2^n)$ possible $i$-moves to consider,
we can indeed find it efficiently using an $s$-$t$ min-cut computation
in a suitably defined graph! (We'll show how to do this in the
answers, or you can think about it.)
\end{enumerate}
\end{document}