Note: Include your Cornell NetID on your each section of your homework. This simplifies the process of recording your grades.
Some friends of your are working with a system that performs real-time scheduling of jobs on multiple servers, and they've come to you for help in getting around an unfortunate piece of legacy code that can't be changed.
Here's the situation. When a batch of jobs arrive, the system allocates them to servers using the simple Greedy-Balance algorithm from the first section of this chapter, which provides an approximation to within a factor of 2. In the decade and a half since this part of the system was written, the hardware has gotten faster to the point where, on the instances that the system needs to deal with, your friends find that it's generally possible to compute an optimal solution.
The difficulty is that the people in charge of the system's internals won't let them change the portion of the software that implements the Greedy-Balance algorithm, so as to replace it with one that finds the optimal solution. (Basically, this portion of the code has to interact with so many other parts of the system that it's not worth the risk of something going wrong if it's replaced.)
After grumbling about this for a while, your friends come up with an alternate idea. Suppose they could write a little piece of code that takes the description of the jobs, computes an optimal solution (since they're able to do this on the instances that arise in practice), and then feeds the jobs to the Greedy-Balance algorithm in an order that will cause it to allocate them optimally. In other words, they're hoping to be able to re-order the input in such a way that when Greedy-Balance encounters the input in this order, it produces an optimal solution.
So their question to you is simply the following: Is this always possible? Their conjecture is,
For every instance of the load balancing problem from the first section of this chapter, there exists an order of the jobs so that when Greedy-Balance processes the jobs in this order, it produces an assignment of jobs to machines with the minimum possible makespan.
Decide whether you think this conjecture is true or false, and give either a proof or a counterexample.
Suppose you are given an n-by-n grid graph G, as in Figure 11.13 in the text. (The figure is an n-by-n grid consisting of n2 nodes; each node, except for those on the boundary, is connected to 4 neighbors, one neighbor in each direction: north, south, east, and west.)
Associated with each node v is a weight w(v), which is a non-negative integer. You may assume that the weights of all nodes are distinct. Your goal is to choose an independent set S of nodes of the grid, so that the sum of the weights of the nodes in S is as large as possible. (The sum of the weights of the nodes in S will be called its total weight.)
Consider the following greedy algorithm for this problem:
The "heaviest-first" greedy algorithm:
Start with S equal to the empty set.
While some node remains in G
Pick a node vi of maximum weight.
Add vi to S.
Delete vi and its neighbors from G.
end while
Return S
Let S be the independent set returned by the "heaviest-first" greedy algorithm, and let T be any other independent set in G. Show that for each node v in T, either v in S, or there is a node v' in S so that w(v) < w(v')$ and (v,v') is an edge of G.
Show that the "heaviest-first" greedy algorithm returns an independent set of total weight at least ¼ times the maximum total weight of any independent set in the grid graph G.
Recall that for a problem in which the goal is to maximize some underlying quantity, gradient descent has a natural "upside-down" analogue, in which one repeatedly moves from the current solution to a solution of strictly greater value. Naturally, we could call this a gradient ascent algorithm (though often in the literature you'll also see such methods referred to as hill-climbing algorithms).
By straight symmetry, the observations we've made in this chapter about gradient descent carry over to gradient ascent: for many problems you can easily end up with a local optimum that is not very good. But sometimes one encounters problems --- as we saw, for example, with the maximum cut and multi-label classification problem (we didn't talk about this topic this year, but you don't need this to solve this problem) --- for which a local search algorithm comes with a very strong guarantee: every local optimum is close in value to the global optimum. We now consider the maximum bipartite matching problem, and find that the same phenomenon happens here as well.
Thus, consider the following gradient ascent algorithm for finding a matching in a bipartite graph:
As long as there is an edge whose endpoints are unmatched, add it to the current matching. When there is no longer such an edge, terminate with a locally-optimal matching.