\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 Fall 2013, CS 583: Approximation Algorithms\\~\\
Homework 6}\\
Due: 12/09/2013
\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
Solve as many problems as you can. I expect at least three for this homework.
\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}
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}
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}
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}
\begin{myprob}
Problem 6.6 from the Williamson-Shmoys book.
\end{myprob}
\begin{myprob}
Problem 15.4 from the Williamson-Shmoys book.
\end{myprob}
\end{document}