Homework 10 (Last One!)

CS 482 - Spring 2005

Due: Friday, May 6 (but may be turned in by noon on Tuesday, May 10, without penalty)

Note: This last homework is due, as usual, on Friday, but because this next Friday is the last day of classes, you may turn the homework in on the following Tuesday without penalty. You are, of course, welcome to turn it in on Friday in class. Homework turned in after class on Friday (and before noon on Tuesday) should be brought to my office (494 Rhodes). If I'm not in the office, just place it under the door.

Note: Include your Cornell NetID on your each section of your homework. This simplifies the process of recording your grades.

Part A

Problem 1 at the end of Chapter 13.
3-Coloring is a yes/no question, but we can phrase it as an optimization problem as follows.

Suppose we are given a graph G = (V,E), and we want to color each node with one of three colors, even if we aren't necessarily able to give different colors to every pair of adjacent nodes. Rather, we say that an edge (u,v) is satisfied if the colors assigned to u and v are different.

Consider a 3-coloring that maximizes the number of satisfied edges, and let c* denote this number. Give a polynomial-time algorithm that produces a 3-coloring that satisfies at least (2/3) c* edges. If you want, your algorithm can be randomized; in this case, the expected number of edges it satisfies should be at least (2/3) c*.

Part B

Problem 3 at the end of Chapter 13.
In the first section of this chapter, we saw a simple distributed protocol to solve a particular contention-resolution problem. Here is another setting in which randomization can help with contention-resolution, through the distributed construction of an independent set.

Suppose we have a system with n processes. Certain pairs of processes are in conflict, meaning that they both require access to a shared resource. In a given time interval, the goal is to schedule a large subset S of the processes to run --- the rest will remain idle --- so that no two conflicting processes are both in the scheduled set S. We'll call such a set S conflict-free.

One can picture this process in terms of a graph G = (V,E) with a node representing each process and an edge joining pairs of processes that are in conflict. It is easy to check that a set of processes S is conflict-free if and only if it forms an independent set in G. This suggests that finding a maximum-size conflict-free set S, for an arbitrary conflict graph G will be difficult (since the general independent set problem is reducible to this problem). Nevertheless, we can still look for heuristics that find a reasonably large conflict-free set. Moreover, we'd like a simple method for achieving this without centralized control: each process should communicate with only a small number of other processes, and then decide whether or not it should belong to the set S.

We will suppose for purposes of this question that each node has exactly d neighbors in the graph G. (That is, each process is in conflict with exactly d other processes.)
1. Consider the following simple protocol.
2. The choice of the probability � in the protocol above was fairly arbitrary, and it's not clear that it should give the best system performance. A more general specification of the protocol would replace the probability � by a parameter p between 0 and 1, as follows:
  
  Each process P_i independently picks a random value x_i; it sets x_i to 1 with probability p and sets x_i to 0 with probability 1-p. It then decides to enter the set S if and only if it chooses the value 1, and each of the processes with which it is in conflict chooses the value 0.
  
  In terms of the parameters of the graph G, give a value of p so that the expected size of the resulting set S is as large as possible. Give a formula for the expected size of S when p is set to this optimal value.

Part C

Problem 7 at the end of Chapter 13.
In class, we designed an approximation algorithm to within a factor of 7/8 for the MAX 3-SAT problem, where we assumed that each clause has terms associated with 3 different variables. In this problem we will consider the analogous MAX SAT problem: given a set of clauses C₁,..., C_k over a set of variables X=x₁,..., x_n, find a truth assignment satisfying as many of the clauses as possible. Each clause has at least one term in it, but otherwise we do not make any assumptions on the length of the clauses: there may be clauses that have a lot of variables, and others may have just a single variable.
1. First consider the randomized approximation algorithm we used for MAX 3-SAT, setting each variable independently to true or false with probability 1/2 each. Show that the expected number of clauses satisfied by this random assignment is at least k/2, i.e., half of the clauses is satisfied in expectation. Give an example to show that there are MAX SAT instances such that no assignment satisfies more than half of the clauses.
2. If we have a clause that consists just of a single term (e.g., a clause consisting just of x₁, or just of not(x₂)), then there is only a single way to satisfy it: we need to set the corresponding variable in the appropriate way. If we have two clauses such that one consists of just the term x_i, and the other consists of just the negated term not(x_i), then this is a pretty direct contradiction.
  Assume that our instance has no such pair of "conflicting clauses"; that is, for no variable x_i do we have both a clause C=x_iand a clause C'=not(x_i). Modify the above randomized procedure to improve the approximation factor from 1/2 to at least a .6 approximation, that is, change the algorithm so that the expected number of clauses satisfied by the process is at least .6k.
3. Give a randomized polynomial time algorithm for the general MAX SAT problem, so that the expected number of clauses satisfied by the algorithm is at least a .6 fraction of the maximum possible.
  (Note that by the example in part (a), there are instances where one cannot satisfy more than k/2 clauses; the point here is that we'd still like an efficient algorithm that, in expectation, can satisfy a .6 fraction of the maximum that can be satisfied by an optimal assignment.)