Local improvement algorithms for a path packing problem: A performance analysis based on linear programming
Operations Research Letters , Volume 49 - Issue 1 p. 62- 68
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|
|Organisation||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