Wednesday, June 22, 2005

Books and some notes

These are some books
  • Golumbic's book or Shamir's notes
  • Schrijver's any of three books: Schrijver1984, Cook... Schrijver, Schrijver2004
  • Schrijver's lecture notes
  • Cornuejols's book


  • An interval graph is perfect. Its interference graph
  • has consecutive 1's property.
  • is TUM

  • --
    the reduction to SAT of the simple cycle problem seems to be easy, look at the standard reduction of ILP to SAT.
    --
    This zero weight cycle problem is something like two flow algorithms running in parallel to each other, checking if the value of one is equal to the other: resulting in a null-weight cycle.
    --
    more importantly, what can be done when the weights belong to 0, \pm 1??????
    gcd?? I meant "any ideas":)
    --
    Check out linear programming when
  • dimension is small
  • when the weights are small: unit distances, in particular

  • Ckeck out the polynomial time linear programming algorithms (Khachiyan-Karmarkar-Karp) from Schrijver and also from Chong. Also, Meggido's algorithm for fixed dimensions
    --
    This seems to be a nice pecking order:
  • linear programming is a black-box-tool that solves all linear problems in polyhedral model, reasonably, with simplex or other ways
  • a smaller problem is scheduling in polyhedral model: till now uses LP: what next?
  • max-flow could also use LP, because of known reasons (TUMity, duality property, etc...). We can crank up the blocking flow enough number of times to obtain a near quadratic algorithm.
  • No comments: