Sunday, June 26, 2005

Notes on Cohen-Megiddo and KMW

Reading Cohen-Megiddo's (CM-Z) paper. Some notes.
The paper does not seem to do a KMW-like decomposition. This is why in the DV-KMW paper, the zero cycle detection of CM-Z result is not used? The algorithm of CM-Z is faster. Also answers the scheduling problem.
--
the papers of KMW, KS, DV-KMW propose a separation of the graph based on some number of calls to LP. KMW propose one per edge, KS propose one ver vertex. DV-KMW propose one call. This results in a sub-graph.
CM-Z call the vector which separates the graph into smaller graphs, a witness. They propose a two step algorithm to compute the witness.
  • how does the two step algorithm work
  • what is the meaning of the witness.
  • what is the difference between the witness of CM-Z and DV-KMW>

    --
    This paper (......) on improved algorithms for LP with two variables per inequality seems to be interesting.
    --
    Look up the result on 1-dimensional scheduling in the CM-Z paper
  • 2 comments:

    al hakanson said...

    thank you. i started reading the book. but its too dualistic. its god in you, not you are god

    al hakanson said...

    i read one of deutschs books i think this one. it was good esp. the part abt. how the world was created & which i could not understand. it almost seemed laughable it was so improbable. i see brahman as the eternal meditator or better put dreamer something which i love to do. can you give me your version of how the 'world' was created. you can contact me at one of my blogs anytime or at hawkuu at excite.com