Coursera

Local Search Algorithms

Quiz

  1. Which of the following statements is NOT true about the generic local search algorithm?

    The generic local search algorithm is guaranteed to eventually converge to an optimal solution

  2. Suppose we apply local search to the minimum cut problem. Given an undirected graph, we begin with an arbitrary cut $(A,B)$. We check if there is a vertex $v$ such that switching $v$ from one group to the other would strictly decrease the number of edges crossing the cut. (Also, we disallow vertex switches that would cause $A$ or $B$ to become empty.) If there is such a vertex, we switch it from one group to the other; if there are many such vertices, we pick one arbitrarily to switch. If there are no such vertices, then we return the current locally optimal cut $(A,B)$. Which of the following statements is true about this local search algorithm?

    This local search algorithm is guaranteed to terminate in a polynomial number of iterations.

  3. In the maximum $k$-cut problem, the input is an undirected graph $G=(V,E)$, and each edge has a nonnegative weight $w_e$. The goal is to partition $V$ into $k$ non-empty pieces $A_1, .., A_k$ to maximize the total weight of the cut edges (i.e., edges with endpoints in different $A_i$’s). The maximum cut problem (as studied in lecture) corresponds to the special case where $k=2$. Consider applying local search to the maximum $k$-cut problem: (i) start with an arbitrary $k$-cut; (ii) repeat: if possible, move a vertex from one set $A_i$ to another set $A_j$ so as to strictly increase the total weight of the cut edges; (iii) once no such move is possible, halt. Consider the following statement: for every instance of the maximum $k$-cut problem, every local maximum has objective function value at least f(k)$ times that of the maximum possible. Which of the following is the biggest choice of the function $f(k)$ for which this statement is true?

    $\frac{k - 1}{k}$

  4. Suppose $X$ is a random variable that has expected value 1. What is the probability that $X$ is 2 or larger?

    At most 100%

  5. Suppose $X$ is a random variable that is always nonnegative and has expected value 1. What is the probability that $X$ is 2 or larger?

    At most 50%