\documentclass[12pt]{article} \usepackage{graphicx} \usepackage{amsmath,amssymb,url} \usepackage{bbm} \newfont{\bssdoz}{cmssbx10 scaled 1200} \newfont{\bssten}{cmssbx10} \oddsidemargin 0in \evensidemargin 0in \topmargin -0.5in \headheight 0.25in \headsep 0.25in \textwidth 6.5in \textheight 9in %\marginparsep 0pt \marginparwidth 0pt \parskip 1.5ex \parindent 0ex \footskip 20pt \begin{document} \parindent 0ex \thispagestyle{empty} \vspace*{-0.75in} {\bssdoz CME 305: Discrete Mathematics and Algorithms} {\\ \bssten Instructor: Reza Zadeh (rezab@stanford.edu) } {\\ \bssten HW\#4 -- Due at the beginning of class Thursday 03/16/17} \vspace{5pt} \begin{enumerate} \item Let $G=(V,E)$ be a $c$-edge connected graph. In other words, assume that the size of minimum cut in $G$ is at least $c$. Construct a graph $G'(V, E')$ by sampling each edge of $G$ with probability $p$ independently at random and reweighing each edge with weight $1/p$. Suppose $c > \log n$, and $\epsilon$ is such that $ \frac{10\log(n)}{c \epsilon^2} \leq 1$. Show that as long as $p \geq \frac{10\log(n)}{c \epsilon^2}$, with high probability the size of every cut in $G'$ is within $(1\pm \epsilon)$ of the cut in the original graph $G$. \item Let $V$ be a finite set. A function $f\colon 2^V \to R$ is submodular iff for any $A,B \subseteq V$, we have $$ f(A \cap B) + f(A \cup B) \leq f(A)+f(B)$$ Now consider a graph with nodes $V$. For any set of vertices $S\subseteq V$ let $f(S)$ denote the number of edges $e=(u,v)$ such that $u\in S$ and $v\in V-S$. Prove that $f$ is submodular. \item A square integer matrix $A$ is {\bf unimodular} if and only if its determinant is $-1$ or $1$. A matrix (not necessarily square) $M$ is {\bf totally unimodular} iff every square submatrix has determinant $1$, $-1$, or $0$, i.e. every non-singular square submatrix is unimodular. Show that for a linear program with totally unimodular constraint matrix $M$ and integral right-hand side $c$, all extreme points must be integral. \item Given a list of personnel ($n$ persons) and of list of $k$ vacation periods, each period spanning several contiguous vacation days. Let $D_j$ be the set of days included in the $j$th vacation period. You need to produce a schedule satisfying: \begin{itemize} \item For a given parameter $c$, each tech support person should be assigned to work at most $c$ vacation days total. \item For each vacation period $j$, each person should be assigned to work at most one of the days during the period. \item Each vacation day should be assigned a single tech support person. \item For each person, only certain vacation periods are viable. \end{itemize} Describe a polynomial time algorithm to generate an assignment or output that no assignment exists. Prove correctness. \item Let $G$ be a graph $n$ nodes and an independent set of size $2n/3$. Give a polynomial time algorithm to find an independent set of size $n/3$ or greater -- find a 1/2-approximation to the independent set in this graph. \item The \textit{directed} cut size is the number of \textit{outgoing} edges from a cut $S$. The directed MAX-CUT problem asks for the cut with maximum directed cut size. Give a $1/4$ approximation algorithm for this problem. \item Online social networks carry a huge potential for online advertising. After a recent controversy, a popular social networking platform does not allow advertisers to target the users individually. However, it is allowed to run ads on user communities. Formally, let $X$ be the set of all users on a social network, and $S_1, S_2, \ldots, S_m$ be subsets of $X$, where each $S_i$ represents a user community. Notice that a user can belong to several communities. Suppose the advertiser can afford placing ads on at most $k$ communities. The goal is to show the ads to as many users as possible, i.e.\ to find $S_{i_1}, S_{i_2}, \ldots, S_{i_k}$ such that $|\cup_{j=1}^{k} S_{i_j}|$ is maximized. Unfortunately, this problem is NP-hard and therefore we are interested in designing efficient approximation algorithms to solve it. Consider the following greedy approach: pick the $k$ communities one at a time, and in each iteration pick the community that contains the largest number of users that have not been covered yet. In other words, choose the community that maximizes the current coverage. Show that this greedy approach yields at least $1 - (1 - 1/k)^k > 1 - 1/e$ fraction of the optimal solution. Hint: Let $x_i$ denote the number of new elements covered by the algorithm in the $i$-th set that it picks. Also, let $y_i=\sum_{j=1}^i x_j,$ and $z_i = OPT - y_i$. Show $x_{i+1} \geq z_i/k$ and prove by induction that $z_i \leq (1 - 1/k)^{i} OPT$. \item The \emph{knapsack problem} is a very well studied NP-hard combinatorial optimization problem. Given $n$ items with (positive) weights $w_1,w_2,\dots,w_n$ and associated values $v_1,v_2\dots,v_n$ and a bag that can hold total weight $W$, determine the number of each items to feasibly place in the bag (total weight chosen at most $W$) to maximize the value of items chosen. Give an algorithm to solve this problem with running time $O(nW)$. Note that in the above version we assume an unlimited supply of every item, but there are variants with limits on each item that can be solved in the same running time in a very similar manner. Finally, note that the above running time is not necessarily polynomial because $W$ is not necessarily polynomial in $n$. \item The \emph{max weight independent set} problem is the following: given an undirected graph $G = (V,E)$ and a weight function on the vertices $w: V \rightarrow \mathbb{R}$, output the independent set of $G$ with the maximum weight, where we define the weight of the set $S$ as $\sum_{v\in S} w(v)$. Our usual notion of maximum independent set problem is just a special case of this problem with all weights equal to 1, so this problem is also NP-hard. However, we can solve it on trees (in fact, if you're interested, we can solve this problem on graphs with bounded treewidth). Give a polynomial time algorithm to solve this problem on trees. \end{enumerate} \end{document}