Given a graph, we wish to find a maximum number of vertex-disjoint paths of length 2. We propose a series of local improvement algorithms for this problem, and present a linear-programming based method for analyzing their performance.

Greedy algorithm, Linear programming, Local search, Path packing, Performance guarantee
Operations Research Letters
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

de Bontridder, K.M.J, Halldórsson, B.V, Halldórsson, M.M, Hurkens, C.A.J, Lenstra, J.K, Ravi, R, & Stougie, L. (2021). Local improvement algorithms for a path packing problem: A performance analysis based on linear programming. Operations Research Letters, 49(1), 62–68. doi:10.1016/j.orl.2020.11.005