due Oct 19

1.  We considered the following load balancing problem in class.  As
    input we have a number m of machines, and times t_1..t_n required
    by n jobs.  We want to assign jobs to processors such that the
    maximum load of the processors is small, where the load of a
    processor is the sum of the times of the jobs allocated to it.

    (a) Suppose we have an additional parameter T which is the maximum
    load allowed for any processor.  Write an IP which which
    expresses this decision problem.

    (b) Write an IP which expresses the original problem.  Hint: if
    you want to minimize the maximum of certain quantities
    q_1,q_2,...,q_m, then define a new variable q, add an equality for
    all i that q_i <= q, and minimize q.

    (c) Run the LP relaxation of the above using a public domain
    program such as lpsolve (available both for linux and windows,
    also excel and oo calc have lpsolvers), with an instance such as
    m=3 and t=1,1,100.  Based on your experiments guess a solution to
    the LP relaxation -- you will see that the optimal LP solution can
    be written down simply even in general.

    If you can guess the LP solution without running the LPs it is
    also fine.  Please submit only the general LP solution.

    (You are expected to observe that for this problem, the IP/LP
    formulation as stated are not too useful, they only give a lower
    bound which is already obvious.)

2.  Consider the naive greedy algorithm for the load balancing
    problem, i.e. the one that considers tasks in the given order
    (without sorting them by times) and places them on the least
    loaded processor.

    (a) Prove that the algorithm obtains a solution which is at most
    2-1/m factor worse than the optimal.  Hint: Get a more accurate
    estimate of the total load than what we did.

    (b) Give an instance for which the algorithm indeed does worse by
    the above factor as compared to the optimal algorithm.

3.  Consider the greedy algorithm for vertex cover: pick the vertex
    which covers the maximum number of edges not covered so far.  Give
    an instance for which this algorithm does not produce an optimal
    solution.