Local improvement algorithms for a path packing problem: a performance analysis based on linear programming

DOI10.1016/j.orl.2020.11.005OpenAlexW3102912034MaRDI QIDQ2661591

R. Ravi, Bjarni V. Halldórsson, K. M. J. De Bontridder, Magnús M. Halldórsson, Jan Karel Lenstra, Cor A. J. Hurkens, Leen Stougie

Publication date: 7 April 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2020.11.005

zbMATH Keywords

linear programminggreedy algorithmlocal searchperformance guaranteepath packing

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items

Approximating the directed path partition problem

Cites Work

• An approximation algorithm for maximum packing of 3-edge paths
• A parameterized perspective on packing paths of length two
• Approximation algorithms for the test cover problem
• An approximation algorithm for maximum triangle packing
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• On the completeness of a generalized matching problem
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)