A local search algorithm for binary maximum 2-path partitioning

Finally we give, by means of bad instances, upper bounds on the performance guarantees of the algorithm. For depth 2 we show a 0.4 upper bound in the subcubic case. For depth 3 we show a 0.6 upper bound, as well as a 0.7 upper bound in the subcubic case. For the general (non-negative) weight problem we show a 0.5556 upper bound for depth 3 (for depth 2, the tight 0.3333 ratio holds for this problem as well).