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.
--
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
Posts
2 comments:
thank you. i started reading the book. but its too dualistic. its god in you, not you are god
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
Post a Comment