\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}
\newcommand{\cR}{\mathbb{R}}
\newcommand{\script}[1]{\mathcal{#1}}
\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 5}\\
Due: 4/27/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.
\iffalse
\begin{myprob}
Consider a variant of the Bandwidth/Resource Allocation Problem from
that we already saw in Homework 2 (Problem 3). Suppose we are given
a path $P$, with an {\em integer} capacity $c_e$ for each edge $e
\in P$. We are also given a set of demand requests $\script{R} =
\{R_1, R_2, \ldots R_m\}$. Each request $R_i$ consists of a pair of
vertices $u_i, v_i$ (interpreted as a request for 1 unit of capacity
from $u_i$ to $v_i$), and a profit $p_i$. The goal is to route a
maximum-profit set of feasible requests; a set of requests is
feasible if, for each edge $e$, the total number of requests that
pass through $e$ is at most $c_e$.
\begin{enumerate}
\item Write a (natural) LP for the Resource Allocation Problem above
with a variable $x_i$ for each request $R_i$.
\item It is known that the matrix corresponding to the LP is totally
unimodular and hence one can obtain an optimum integral solution
via the LP. In this problem we will use a different approach to
prove the optimality of the LP via iterated rounding. The goal is
to prove that any basic feasible solution $x$ to the LP there is
some $i$ such that $x_i = 1$. Prove this using the following
hints.
\emph{Hint 1: Let $x$ be a basic feasible solution and
$\script{R'}$ be the set of requests with $x_i \in (0,1)$, and
$n = |\script{R'}|$. Consider the set of tight constraints
(edges) which determine $x$. There must be $n$ of them and the
rows associated with them must be linearly independent. Obtain a
contradiction by using a counting argument to show that there
can be at most $n-1$ of them using the next hint.}
\emph{Hint 2: Let $e_1, \ldots, e_n$ be the tight edges from left
to right where $e_i = (\ell_i, r_i)$. First, suppose that the
entire path consists of tight edges. Prove that for each $e_i$
there must be at least $2$ demands from $\script{R'}$ that start
or end at $\ell_i$ and $2$ demands that start or end at $r_i$;
otherwise $e_i$ will not be linearly independent from $e_{i-1}$
and $e_{i+1}$, or $e_i$ will not be tight; use the fact that
capacities are integer valued and $x_i$ are in $(0,1)$.}
\emph{If not all path edges are tight, try to contract some edges on
the path.}
\end{enumerate}
\end{myprob}
\fi
\begin{myprob}
Problem 11.6 from Shmoys-Williamson book.
\end{myprob}
\begin{myprob}
In the Node-weighted Multiway Cut problem we are given an undirected
node-weighted graph $G=(V,E)$, $k$ terminal nodes $S = \{s_1,s_2,\ldots,s_k\}$.
Node $v$ has a non-negative weight $c_v$. The goal is to remove a minimum
weight subset of nodes $V' \subset V$ such that $G-V'$ has no path
from $s_i$ to $s_j$, $1 \le i < j \le k$. Assume for simplicity that
terminals cannot be removed (they have infinite weight) and that they
form an independent set (so that there is a feasible solution).
Consider the following LP relaxation where there is a variable $x_v$
for each $v \in V \setminus S$ indicating whether to remove $v$.
Let $\mathcal{P}_{u,v}$ denote the set of all paths from $u$ to $v$ in $G$.
\begin{eqnarray*}
\min \sum_{v \in V} c_v x_v && \\
\sum_{v \in p} x_v &\ge & 1 \quad \quad p \in \mathcal{P}_{s_i,s_j}, i \neq j\\
x_v & \ge & 0 \quad \quad v \in V
\end{eqnarray*}
Let $\bar{x}$ be a feasible solution to the LP.
Define $B_{\bar{x}}(s,r)$
where $s \in V$ and $r$ is a real number to be the set of all
nodes $v$ such that there is a path $P$ from $s$ to $v$ such that
$(\sum_{u \in P} \bar{x}_u) - \bar{x}_v < r$. That is, we are counting only the
length of the nodes in the path other than the endpoint $v$.
Consider the following rounding algorithm. First remove all nodes
$v$ such that $\bar{x}_v \ge 1/3$. Second, pick a $\theta$ uniformly
at random from $(0,1/3)$ and for each $s_i$ remove all nodes that are
adjacent to $B(s_i,\theta)$ but not in $B(s_i,\theta)$. Prove that
for any $\theta$ the removed nodes form a multiway cut and that the
expected weight of the nodes removed is at most $3\sum_v c_v x_v$.
\end{myprob}
\begin{myprob}
In the $k$-tree problem you are given an undirected edge-weighted
graph $G=(V,E)$ with edge weights $c:E\rightarrow \cR^+$ and an
integer $k$. The goal is to find a tree $T=(V_T,E_T)$ in $G$ of
smallest edge weight ($\sum_{e \in E_T} c(e)$) such that $|V_T| \ge
k$. Show that if there is an $\alpha$-approximation for $k$-tree
then there is an $\alpha$-approximation for the Steiner tree
problem. Recall that in the Steiner tree problem, the input is an
edge-weighted graph $G=(V,E)$ and a set of terminals $S \subseteq
V$; the goal is to find a tree $T$ of minimum edge-weight that
connects (contains) all the terminals $S$.
\end{myprob}
\begin{myprob}
In this problem you will derive an $O(\log k \cdot \log n)$
approximation for the rooted $k$-Steiner-tree problem which is
related to the previous problem. The input consists of an
edge-weighted undirected graph $G=(V,E)$, a specified root vertex
$r$ and a set $S \subset V$ of terminals. The goal is to find a
min-cost tree $(V_T,E_T)$, a sub-graph of $G$, such that $r \in V_T$
and $|S \cap V_T| \ge k$. Obtain an approximation for this problem
following the outline below.
\begin{itemize}
\item Consider the density variant of the problem where the goal is
to find a tree $T=(V_T,E_T)$ rooted at $r$ that minimizes the
ratio $c(E_T)/|V_T \cap S|$. Write an LP relaxation for this
problem using ideas similar to the one for Sparsest Cut (and
Steiner tree). Using the scaling idea used to reduce
Sparsest Cut to Multicut, reduce the density variant of
$k$-Steiner-tree to the Steiner tree problem and obtain an $O(\log
n)$ approximation. Recall that the Steiner tree LP has an
integrality gap of $2$.
\emph{See Lecture 19 from spring 2009, and Prob 8.6 from
the Shmoys-Williamson book to learn about the scaling idea
mentioned.}
\item Use an approximation algorithm for the density variant above
in an iterative greedy fashion to create a tree rooted at $r$ with
at least $k$ terminals. What is the density of this tree when
compared to the density of the optimal solution to the original
$k$-Steiner-tree problem?
\item If the tree you have in the previous step has many more than
$k$ terminals, {\em prune} it to have $k'$ terminals where $k \le
k' \le 2k$ such that the density of the resulting tree is not much
worse than the tree you started with.
\item How can you connect the pruned tree to the original root $r$
without incurring too much cost? Assuming you know the optimal
cost, can you preprocess the instance to ensure that this
connection cost is not too much?
\end{itemize}
\end{myprob}
\begin{myprob}
Consider the feedback edge set problem (FES). The input is an
edge-weighted undirected graph $G=(V,E)$ and the goal is to remove a
minimum-weight set $E'\subset E$ such that $G-E'$ has no cycles.
Note that FES can be solved in polynomial-time by taking the complement
of a maximum-weight spanning tree. Nevertheless we will consider
an analysis based on the following natural LP. There is a variable
$x_e$ for each $e \in E$ that indicates whether to remove $e$.
\begin{eqnarray*}
\min \sum_{e \in E} c_e x_e && \\
\sum_{e \in C} x_e &\ge & 1 \quad \quad \mbox{for each cycle $C$}\\
x_e & \ge & 0 \quad \quad e \in E
\end{eqnarray*}
\begin{itemize}
\item Assuming the existence of a constant degree graphs whose {\em
girth} is $\Omega(\log n)$ (the degree is bigger than 2
otherwise the cycle is an easy example) prove that the integrality
gap of this LP is $\Omega(\log n)$. The girth of a graph is the
length of its shortest cycle.
\item We saw an upper bound of $O(\log n)$ via the primal-dual technique.
See Section 7.2 in Williamson-Shmoys book for the more general
Feedback Vertex Set problem. Here we will see a proof via a reduction
to the Multicut analysis. Given a feasible solution $\bar{x}$ for the
LP for FES define a Multicut instance where each a pair of vertices
$uv$ is to be separated of $d_{\bar{x}}(uv) \ge 1/3$; that is, the
distance from $u$ to $v$ according to edge-lenghts given by $\bar{x}$ is
at least $1/3$. Define a feasible fractional solution for this
Multicut instance on $G$ by appropriately scaling up $\bar{x}$ and
use the Multicut analysis to give an $O(\log n)$ upper bound on
the integrality gap of the LP.
\item {\em Extra Credit:} Use the above ideas to obtain an $O(\log
n)$-approximation for the Subset Feedback Edgeset problem. Here we
are given edge-weighted graph $G=(V,E)$ and a subset of terminals
$S = \{s_1,\ldots,s_k\}$ and the goal is to remove a minimum-weight
set of edges $E'$ such that $G-E'$ has no cycle containing a terminal.
\end{itemize}
\end{myprob}
\begin{myprob}
Prove that any ring metric isometrically embeds into $\ell_1$.
\end{myprob}
\begin{myprob}
Given a graph $G=(V,E)$ with edge-weights $c:E \rightarrow \cR^+$,
you wish to partition $G$ into $G_1=G[V_1], G_2=G[V_2], G_3=G[V_3]$
such that $\lfloor |V|/3 \rfloor \le |V_i| \le \lceil |V|/3 \rceil$
for $1\le i \le 3$, and the cost of the edges between the partitions
is minimized. Using an $\alpha$-approximation for the sparsest cut
problem, give a pseudo-approximation for this problem where you
partition the graph into $3$ pieces $G[V_1'],G[V_2'],G[V_3']$ such
that $|V|/c_2 \le |V'_i| \le |V|/c_1$ for some constants $1 < c_1 <
c_2$ and the cost of the edges between the partitions is $O(\alpha)
\opt$. What constants $c_1, c_2$ can you guarantee? Note that $c_1$
and $c_2$ should be \emph{constants}, independent of the graph
size. (Hint: this problem is similar to the one on partitioning into
two pieces that is in Vazirani's book on applications of sparsest cut
(Section 21.6.3).)
\end{myprob}
\iffalse
\begin{myprob}
Problem 8.9 from Shmoys-Williamson book. This is to make you read
Section 8.6 on buy-at-bulk network design.
\end{myprob}
\fi
\end{document}