\documentclass{article} \input{6856-preamble} \begin{document} \psetnum{6} \date{2005/03/16} \collab{Collaborators: $\set{\mathtt{sarahl}, \mathtt{gpickard}}$} \begin{pset} \begin{problem} \begin{subproblem} We claim that the set of vertices output over all phases is a maximal independent set. It is an independent set because during each phase, one vertex corresponding to every edge is deleted, so no adjacent vertices are added during one phase, and the neighbors of every vertex are deleted, so no adjacent vertices are added during the next phase. We can see that it is maximal because a vertex is deleted only when it is added to the set or when one of its neighbors is added. Since there are no vertices remaining at the end, one of these is true in every vertex. So the set is maximal because no more vertices can be added. \end{subproblem} \begin{subproblem} Suppose a vertex $v$ has degree $d$. The vertex remains marked as long as it is the lower-weight endpoint of each of its edges, i.e. if it has lower weight than any of its $d$ neighbors. Since the weights of the vertices are determined uniformly at random, we can consider their relative rankings to be uniformly distributed. Thus, in the set consisting of $v$ and its $d$ neighbors, $v$ has the lowest weight with probability $\frac{1}{d+1}$. This analysis assumes that no two vertices are assigned the same weight. We will ensure that unique weights are assigned to the vertices by checking whether any two vertices have the same weight, and if so generating new random weights, and repeating if necessary. This can be performed in parallel using one processor per pair of vertices. The probability that two vertices are assigned the same weight from a set of $n^4$ weights is $\frac{n}{n^4} = \frac{1}{n^3}$, which is small enough that with high probability $\log n$ attempts will succeed. \end{subproblem} \begin{subproblem} We use the same definition of a good vertex: a vertex $v$ is good if it has at least $\frac{d(v)}{3}$ neighbors of degree no more than $d(v)$. We claim that a good vertex is removed from the graph in a given phase with constant probability. A vertex is removed from the graph if it or one of its neighbors remains marked. We consider the probability of some neighbor of a good vertex $v$ being selected for the IS. Each neighbor $u$ will be added to the IS with probability $\frac{1}{d(u) + 1}$ from above. Since $v$ is good, it has at least $\frac{d(v)}{3}$ neighbors of degree no more than $d(v)$. Each of these neighbors will be selected for the IS with probability at least $\frac{1}{d(v) + 1}$, so the probability that $v$ is removed in a given phase is at least \[ \frac{\frac{d(v)}{3}}{d(v) + 1} = \frac{1}{3 + \frac{3}{d(v)}} \ge \frac{1}{6} \] since $d(v)$ is at least 1. Now we have proven that a good vertex is removed from the graph in a given phase with constant probability. In class we showed that if any edge with a good neighbor has constant probability $\alpha$ to be removed --- which Ģis precisely what we have just proven --- $\bigO{\log m}$ iterations suffice to reduce the number of edges by a polynomial factor, and so we have a $\RNC$ algorithm. \end{subproblem} \end{problem} \begin{problem} We want to determine the successor matrix representation of the all-pairs shortest path in a graph where edge lengths are integers from $1$ to $B$. Recall that we can perform a witnessed Boolean matrix multiplication in $\bigO{MM(n) \log^2 n}$ time. We modify Seidel's algorithm slightly to handle the non-unit edge lengths. The distance between two neighboring vertices $i$ and $k$ and some other vertex $k$ no longer differs by 1 but rather by $B$, so we have the inequalities \begin{align} \label{eq:pmb} \forall k &\;\; D_{ij} - B \le D_{kj} \le D_{ij} + B \\ \label{eq:existsk} \exists k &\;\; D_{kj} = D_{ki} + D_{ij} \end{align} Rather than consider distances mod 3 as in Seidel's algorithm, we consider distances mod $2B + 1$. % For neighbors $i$ and $k$, if % $D_{ij} \equiv D_{ki} + D_{ij} \pmod{2B+1}$ then $D_{ij} = D_{ki} % + D_{ij}$ by Equation~\ref{eq:pmb}. If $k$ is a neighbor on the shortest path from $i$ to $j$, then $D_{kj} = D_{ki} + D_{ij}$; by Equation~\ref{eq:pmb} this is true if and only if $D_{kj} \equiv D_{ki} + D_{ij}$, and by Equation~\ref{eq:existsk} a neighbor $k$ satisfying this condition must exist. We define the Boolean matrix $D^{(s)}$ to have $D^{(s)}_{kj} = 1$ iff $D_{kj} \equiv s \pmod{2B+1}$. Then $k$ is on the shortest path from $i$ to $j$ if $D_{ij} = D_{ik} + D_{kj}$, which is the case when there exists some integer $x$ ($1 \le x \le 2B+1$) such that $D^{(x)}_{ik} = 1$ and $D^{(D_{kj} - x \bmod 2B+1)}_{kj} = 1$. This is exactly when $\left(D^{(x)} D^{(D_{kj} - x \bmod 2B+1)}\right)_{ij} = 1$. Furthermore, we can use a witnessed Boolean matrix multiplication of these two matrices to identify the successor $k$. Define $W^{(x,d)}$ to be the witnessed product $\left(D^{(x)} D^{d - x \bmod 2B+1)}\right)$. Since computations are performed modulo $2B+1$, there are only $\bigO{B}$ possible values for and $x$ and $d$, and so we can compute all the $W^{(x,d)}$ matrices with $\bigO{B^2}$ witnessed multiplications. Then it is straightforward to compute our successor matrix from these: \[S_{ij} = W^{(x, D_{ij})} \text { for any } x \text { such that } W^{(x, D_{ij})}\text{ is non-zero.}\] This algorithm requires $\bigO{B^2 MM(n) \log^2 n}$ time. \end{problem} \begin{problem} We consider the problem of finding a minimum-weight perfect matching in a bipartite graph $G$. Our algorithm is essentially the same as in the unweighted case, except that the edges now have initial weight. As before, we generate a graph $G'$ that is likely to have a unique perfect matching. We do so by scaling up the initial edge weights by a factor of $4mn$, then adding a perturbation selected uniformly at random from $1$ to $2m$. The remainder of the algorithm is exactly as in the unweighted case. To show correctness, we first show that a minimum-weight matching $\alpha$ in $G'$ will indeed always be a minimum weight matching in the original graph $G$. The matching is minimum weight in $G'$, so no other matching has lower weight in $G'$. The only case in which this would not be a minimum-weight matching in $G$ would be if there were some other matching $\beta$ that had lower weight in $G$ but higher weight in $G'$. We show that this is impossible. Let $w_{\alpha}'$ be $\alpha$'s weight in $G'$, and $w_{\alpha}$ be $\alpha$'s weight in $G$. By definition, $w_{\alpha}' = (4mn)w_\alpha + x$ for some perturbation $x$. Similarly, $w_\beta' = (4mn)w_\beta + y$ for some other perturbation $y$, which is at least $(4mn)(w_\alpha + 1) + y$, since edge weights are integers. So \[ w_\beta' - w_\alpha' \ge (4mn)(w_\alpha + 1) + y - \left((4mn)w_\alpha + x\right) = 4mn + y - x \] But $y$ and $x$ are the total perturbations on a matching; since each matching has $n$ edges and each edge receives perturbation at most $2m$, $x$ and $y$ are both bounded by $2mn$. So $w_\beta' - w_\alpha'$ will never be negative and so $\beta$ with lower weight in $G$ but higher weight in $G'$ can exist. Now we need only show that it is likely that $G'$ will have a unique minimum-weight perfect matching. The proof is based on the Isolating Lemma. First, note that the result above proves there is no danger of a perfect matching with minimum weight in $G$ becoming a minimum-weight matching in $G'$. So we can safely ignore all perfect matchings that do not have minimum weight in $G$. Let $\mathscr{F}$ be the set of perfect matchings with minimum weight in $G'$. Each of these matchings has the same weight; call it $w$. So we can subtract away each edge's initial weight, reducing the set system to the unweighted case. This gives a set system $(X, \mathscr{F})$ where $X$ is the set of (now unweighted) edges, and each edge receives a random weight chosen uniformly and independently from $1$ to $2m$. The isolating lemma tells us that there is a unique minimum weight set in $\mathscr{F}$ with probability at least $\nicefrac12$. This means that with probability $\nicefrac12$, there is a perfect matching in $\mathscr{F}$ that has a unique minimum perturbation added to it. Since every perfect matching in $\mathscr{F}$ had minimum weight in $G'$, a matching in $\mathscr{F}$ with unique minimum perturbation is a unique minimum-weight perfect matching, and so our algorithm for finding unique minimum-weight perfect matchings can find it. This proves the claim. Note that this algorithm is clearly in $\RNC$ because the scaling and random perturbation of edge weights can be performed in parallel, then the $\RNC$ algorithm for finding the matching can be applied. \end{problem} \begin{problem} \begin{subproblem} Define $Y$ to be the random variable giving the number of hits that occur with $n$ samples, i.e. $X = \sum_{i=1}^n I_i$. Certainly $\Exp{X} = np$ and so our estimator is $\hat{p} = \frac1n Y$. We wish to obtain a $\hat{p}$ such that $\Pr{\abs{\hat{p}-p} > \epsilon} \le \delta$. Equivalently, $\Pr{\abs{Y-np} > n\epsilon} \le \delta$. Recall the additive form of the Chernoff bound: \begin{lemma}[Chernoff] If $X$ is a sum of $n$ independent random variables with mean $\mu$, then \begin{align*} \Pr{X-\mu > n\epsilon} &\le e^{-2n\epsilon^2} \\ \Pr{X-\mu < -n\epsilon} &\le e^{-2n\epsilon^2} \end{align*} \end{lemma} This gives the immediate corollary that \[ \Pr{\abs{X-\mu} > n\epsilon} \le 2e^{-2n\epsilon^2} \] We can apply this bound to $Y$, since it is a sum of independent indicator random variables. Since $\mu_Y = np$, we obtain \[ \Pr{\abs{Y-np} > n\epsilon} \le 2e^{-2n\epsilon^2} \] We want this to occur with probability at most $\delta$, so \begin{align*} 2e^{-2n\epsilon^2} &\le \delta \\ -2n\epsilon^2 &\le \ln \nicefrac\delta2 \\ 2n\epsilon^2 &\ge \ln \nicefrac2\delta \\ n &\ge \frac{1}{2\epsilon^2} \ln \nicefrac2\delta \end{align*} \end{subproblem} \begin{subproblem} Suppose we have an estimation algorithm that estimates $p$ to within a multiplicative factor of $(1 \pm \epsilon)$ with error probability $\nicefrac14$ and wish to reduce this error probability to some $\delta$ by performing $k$ estimations and taking the median. We give a bound on $k$ as a function of $\delta$. Let $X$ be the median of $k$ estimations. We first consider $\Pr{X > (1+\epsilon) p}$. Note that this only occurs if at least $\nicefrac k2$ of the estimations are greater than $(1+\epsilon)p$. Define $I_i$ to be the indicator random variable that takes value 1 if the $i$th trial exceeds $p$ by a factor of $1+\epsilon$. By definition, $\Pr{I_i = 1} \le \nicefrac14$. Then define $Y = \sum_{i=1}^k I_i$, $\Pr{X > (1+\epsilon) p} = \Pr{Y > \nicefrac k2}$. So \begin{align*} \Pr{X > (1+\epsilon) p} = \Pr{Y > \frac k2} &\le \binom{k}{\frac{k}{2}} \left(\frac{1}{4}\right)^{\nicefrac{k}{2}} \\ &\le \left(\frac{ke}{\frac{k}{2}}\right)^{\nicefrac{k}{2}} \left(\frac{1}{4}\right)^{\nicefrac{k}{2}} \\ &\le \left(\frac{e}{2}\right)^{\nicefrac{k}{2}} \end{align*} Now we want to ensure that this is less than $\delta$. So \begin{align*} %\Pr{X > (1+\epsilon) p} \le \left(\frac{e}{2}\right)^{\nicefrac{k}{2}} &\le \delta \\ \frac{k}{2} \ln \frac{e}{2} &\le \ln \delta\\ k &= \bigO{\log \delta} \end{align*} \end{subproblem} \end{problem} \end{pset} \end{document}