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