Reference no: EM133371669

Question 1. Suppose we are given the following graph. We need the sampling to be done with the steady state probability distribution of a random walk to be Π (a) = 1/5,  Π (b) = 1/6, Π (c) = 2/15, Π(d) = 1/5, Π(e) = 1/6, Π(f) = 2/ 15. What should the transition probabilities be to guarantee the needed steady state distribution?

Question 2. Consider the problem of finding a stable state in a Hop field neural network, in the special case when all edge weights are positive. This corresponds to the Maximum-Cut Problem that we discussed earlier in the chapter: For every edge e in the graph G, the endpoints of G would prefer to have opposite states. Now suppose the underlying graph G is connected and bipartite; the nodes can be partitioned into sets X and Y so that each edge has.one end in X and the other in Y. Then there is a natural "best" configuration for the Hopfield net, in which all nodes in X have the state +1 and all nodes in Y have the state -1. This way, all edges are good, in that their ends have opposite states.

The question is: In this special case, when the best configuration is so clear, will the State- Flipping Algorithm described in the text (as long as there is an unsatisfied node, choose one and flip its state) always find this configuration? Give a proof that it will, or an example of an input instance, a starting configuration, and an execution of the State- Flipping Algorithm that terminates at a configuration in which not all edges are good.

Question 3. Suppose you're consulting for a biotech company that runs experimentson two expensive high-throughput assay machines, each identical, which we'll label M1 and M2. Each day they have a number of jobs that they need to do, and each job has to be assigned to one of the two machines. The problem they need help on is how to assign the jobs to machines to keep the loads balanced each day. The problem is staied as follows. There are n jobs, and each job j has a required processing time tj. They need to partition the jobs into two groups A and B, where set A is assigned to M₁ and set B to M₂. The time needed to process all of the jobs on the two machines is |T₁ -T₂| = ∑_j∈A t_j and T₂ = ∑_i∈B t_i. The problem is to have the two machines work roughly for the same amounts of time--that is, to minimize |T1 - T2|.

A previous consultant showed that the problem is NP-hard (by a reduction from Subset Sum). Now they are looking for a good local search algorithm. They propose the following. Start by assigning jobs to the two machines arbitrarily (say jobs 1 ... n/2 to M₁, the rest to M₂). The local moves are to move a single job from one machine to the other, and we only move jobs if the move decreases the absolute difference in the processing times. You are hired to answer some basic questions about the performance of this algorithm.

(a) The first question is: How good is the solution obtained? Assume that there is no single job that dominates all the processing time - that is, that t_j ≤ 1/2 ∑_i=1ⁿ t₁; for all jobs j. Prove that for every locally optimal solution, the times the two machines operate are roughly balanced:

1/2 T₁ ≤ T₂ ≤ 2T₁

(b) Next you worry about the running time of the algorithm: How often will jobs be moved back and forth between the two machines? You propose the following small modification in the algorithm. If, in a local move, many different jobs can move from one machine to the other, then the algorithm should always move the job j with maximum t_j. Prove that, under this variant, each job will move at most once (hence algorithm terminates in at most n steps)