Saturday, June 18, 2005

TUMity of gray and degray matrices

The matrices which are used to convert from a "real" to gray and back again are total-unimodular. What does this mean in a linear algebraic way? What does this mean in a graph theoretic way?
--
Postscript: The paper by Conforti et. al is a very interesting one.
  • It classifies a set of SAT problems that can be solved in polynomial time (I noticed this property from the dense book by the second author).
  • For a JACM paper, it is very short, mainly consisting of one main proof.
  • What are its implications on a search algorithm? In specific, how does this property help solving SAT using GA or the more general problem of GRAY/BINARY representations?

  • --
    Postscript: Consider a deterministic algorithm. randomize it, and call it a GA. If we define a new space which the GA looks at, it is working like a simplex algorithm by doing a neighbourhood search.

    No comments: