REMINDERS: hw5 program due this evening, hw5 written (3 problems) due
Monday.  We'll have some review and evaluations on Monday, more review
Wednesday (11am W302, with hw5 solutions), and the final exam 4:30pm
Friday.  Remember you can bring one sheet of notes to the final exam.

Today: Reductions (see book pages 903-907), and
       LP (pages 907-909, first pages of 99LinearProgramming.pdf)

Suppose A and B are computational problems.  When we "reduce A to B",
that means that if we have an efficient solver for problem B, then we
can use that (as a subroutine) to get an efficient solver for A.  We
say we have a "reduction from A to B".  We can think of it an an
inequality of difficulty, "A <= B", meaning "A is no harder than B".
(Technical caveat: the usual definition for efficient is simply
"polynomial time", which may be too loose in practice.)

Examples:
   Reduce median-finding to sorting.
   Reduce maximum bipartite matching to maxflow.
   Reduce BWT (forward transform) to suffix sorting.
   Reduce 2D Euclidean MST to the Delaunay triangulation.

Suppose X is a new problem, and you would like to solve it.
Reductions have two kinds of uses:

    An "upper bound" X<=Y, where Y is solved:
      This gives you a quick solution for X.
      (You might still look for a faster direct solution.)

    A "lower bounds" Y<=X, where Y is hard:
      This is evidence that X is hard, too.
      Example: all problems in "NP" reduce to TSP.
      (But, open problem: we only "suspect" they are hard.)

I'll leave the hard NP/TSP stuff for CS424 (the theory course).

Today instead I'll look at a particularly useful "solved" problem:
Linear Programming (LP).  LP has three things going for it:

  1. it has good practical solvers (we will use one, lp_solve).
  2. it has good worst case solvers (polynomial time).
  3. we can reduce many interesting problems to LP.

I don't have time to take you through 1 (the simplex algorithm) and 2
(the ellipsoid algorithm).  But we will define LP, and see
some aplications (point 3).

LP solves an optimization problems where we have real variables,
several linear inequalities (constraints) on those variables, and a
linear objective (that we want to maximize or minimize).  For an
introduction, we'll look at the slides (maybe first 10-16 pages).

We have various small example LP problems in today's directory (*.lp
files, also one *.ip).  We can solve these using the "solve" script
(which calls lp_solve, an open-source simplex solver).

Running the solver:
    ./solve foo.lp

In fact there is a "duality" theory for LP problems (see Duality.txt
for the details), so that for every maximization problem, there is a
"dual" minimization problem with the same value.

So our examples come in "dual pairs":

  fc-max.lp, fc-min.lp  -- duals: maxflow and mincut (both values 7)
  sp-max.lp, sp-min.lp  -- duals: shortest-path and mincost flow (both 7)

In the previous problems, their optimal values are always achieved
using integer values (0/1, in fact).  But that is not true of all LP
problems.  This is a dual pair with "fractional" solutions:

  vm-max.lp, vm-min.lp  -- duals: frac matching and vertex-cover (both 2.5)

If we modify the LP to require *integer* values of the variables,
then we get another problem called integer programming (IP).
It turns out that IP is much harder, just like TSP (we can reduce
TSP and IP to each other).  IP versions of the previous problem:

  vm-max.ip, vm-min.ip  -- IP versions of the last pair (values 2 and 3)

Of those, the first IP problem (vm-max, "max matching" in a graph) is
always solvable in polynomial time, by a classic algorithm of Edmonds
(a bit trickier than the bipartite case). The second IP problem
(vm-min, "min vertex cover") is instead NP-hard (as hard as TSP and
IP), so we do not expect a polynomial time algorithm for it.