HOMEWORK 1  (try to do these over the weekend).

--- (0) Give the simplest example you can of a linear program with only integer
coefficients (that is, all numbers appearing in the constraints or in the
objective function are integers) that does not have an optimal integer
solution.  Recall that an integer solution is one in which the variables take
on only integer values.

--- (1) Why does the assignment Pi(u) := dist(s,u) give a feasible solution to
the dual of the linear program for shortest paths (defined in lecture 2)?  Why
do this and general facts about linear programming duality imply that the
original LP (linear program) always has an optimal integer solution?

----- background for remaining problems:

Given a graph G=(V,E), recall that a "cut" (defined by any subset S of the
vertices) is the set of EDGES with one endpoint in S and the other not in S.

The MAX-CUT problem is to find a cut of maximum size (#edges).  We mentioned in
lecture 1 that this was NP-hard.

The MIN-ST-CUT problem is, given G and two vertices s and t, to find a cut of
minimum size among those separating s and t.  (That is, s and t should be on
opposite sides of the cut.)

Consider the following two (not-quite linear) programs:

(a) Maximize sum_{uv in E} |Pi_u - Pi_v| 
  subject to 0 <= Pi_u <= 1 for u in V.

(b) Minimize sum_{uv in E} |Pi_u - Pi_v| 
  subject to 0 <= Pi_u <= 1 for u in V
         and Pi_s = 0 and Pi_t = 1.

To make sure you understand the notation, the above sum is the sum, over all
edges (u,v) in E, of the absolute value of Pi_u - Pi_v.  (The underscore means
the subsequent item should be a subscript of the preceding one.)

These are not linear programs because the absolute-value function is not a
linear function.

--- 2) For each of these programs, show that for any feasible solution Pi,
there is a feasible INTEGER solution Pi' that is as good (w.r.t. the cost).  A
hint is available.

--- 3) Argue that (a) and (b) are equivalent to MAX-CUT and MIN-ST-CUT resp.

--- 4) Describe a linear program equivalent to program (b).  Why does this mean
that MIN-ST-CUT is in P?  Can you describe a similar equivalent to program (a)?

-- *5) Can you come up with ANY linear program for MAX-CUT such that the
optimum is at most 2 times the size of the max. cut?