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: