\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 6}\\
Due: 5/9/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 2 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.
\begin{myprob}
Given an $n \times n$ matrix $A$, a \emph{principal submatrix} of
$A$ is a square submatrix obtained by picking a set of indices $S
\subseteq \{1, 2, \ldots, n\}$, and discarding the rows \emph{and}
columns of $A$ indexed by $S$. For instance, the principal submatrix
of $A$ corresponding to $S = \{1,4,5\}$ is the $(n-3) \times (n-3)$
matrix obtained from $A$ by discarding rows $1,4,5$ and columns
$1,4,5$.
Prove that \emph{all} the principal submatrices of a positive
semidefinite matrix are also positive semidefinite. (Which
characterization of positive semidefinite matrices can you use?)
Conclude that if a matrix $A$ is positive semidefinite, the
determinant of any principal submatrix of $A$ is nonnegative.
(\emph{Note:} The converse is also true, though you do not have to
prove it: If the determinants of all principal submatrices of a real
symmetric matrix $A$ are nonnegative, $A$ is positive semidefinite.)
\end{myprob}
\begin{myprob}
Consider MAX-CUT with the additional constraint that specified pairs
of vertices be on the same/opposite sides of the cut. Formally, we
are given two sets of pairs of vertices, $S_1$ and $S_2$. The pairs
in $S_1$ need to be separated, and those in $S_2$ need to be on the
same side of the cut sought. Under these constraints, the problem is
to find a maximum-weight cut.
\begin{enumerate}
\item Give an efficient algorithm to check if there is a
\emph{feasible} solution.
\item Assuming there is a feasible solution, give a strict quadratic
program and vector program relaxation for this problem. Show how
the algorithm for MAX-CUT we saw in class can be adapted to this
problem while maintaining the same approximation ratio.
\end{enumerate}
\end{myprob}
\begin{myprob}
Problem 6.6 from the Williamson-Shmoys book. SDP for directed cut.
\end{myprob}
\begin{myprob}
In this problem you will consider the {\em node-weighted} Steiner
tree problem. The input consists of an undirected graph $G=(V,E)$
and a subset $S \subseteq V$ of terminals. Each node $v$ has a
non-negative weight $w(v)$. The goal is to find a minimum weight
subset of nodes $S'$ such that the subgraph induced on those nodes
$G[S']$ connects all terminals. One can equivalently phrase it as
finding a tree $T$ in $G$ that contains all the terminals with the
goal of minimizing the weight of the nodes in $T$. It is useful to
assume that the terminals have zero weight since they have to be
included anyway.
\begin{itemize}
\item Show that an $\alpha(|S|)$-approximation for the above problem
implies an $\alpha(n)$-approximation for the set cover problem on
$n$ elements.
\item Derive an $O(\log |S|)$-approximation as follows. A {\em spider}
is a tree in which at most one node has degree more than $2$.
For example a path is a spider. If a spider is not a path then
let $v$ be the node with degree strictly more than $2$. Then the
spider consists of paths $P_1,\ldots, P_k$ that are node-disjoint
except at $v$. Given a spider let its density be the ratio of the
weight of its nodes to the number of terminals it contains.
\begin{itemize}
\item Let $T^*$ be a tree that contains the terminals. Then show
that there is a spider in $T^*$ of density at most $w(T^*)/|S|$.
\item Show how one can compute a minimum density spider in polynomial time.
\item Combine the above two to derive the $O(\log
n)$-approximation.
\end{itemize}
\end{itemize}
\end{myprob}
\end{document}