eccd2a86bae4728b38627162ba297828-Supplemental.pdf

For the base case, we consider the first pick, and suppose thati1 6= l1 (and so l1 does not occur inP). Thereasoningnowcanbe mimicked again, and so we can construct another optimal solution such that therth choice is also greedy. This sorting operation can be achieved in log-linear time. Clearly,anyotherdescendant nodes(atwhichatleastoneofδr+1,...,δn is 1) would not satisfy (C2) and hence does not need to be considered.