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
    • at

    2 comments:

    1. al hakansonSun Jun 26, 07:50:00 PM GMT+2

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

      ReplyDelete
    2. al hakansonMon Jun 27, 06:56:00 PM GMT+2

      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

      ReplyDelete