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

Koen M.J. De Bontridder, B.V. Halldórsson, Magnús M. Halldórsson, Cor A.J. Hurkens (Corresponding author), J.K. Lenstra, R. Ravi, L. Stougie

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)62-68
Number of pages7
JournalOperations Research Letters
Volume49
Issue number1
DOIs
Publication statusPublished - Jan 2021

Keywords

  • Greedy algorithm
  • Linear programming
  • Local search
  • Path packing
  • Performance guarantee

Fingerprint Dive into the research topics of 'Local improvement algorithms for a path packing problem: a performance analysis based on linear programming'. Together they form a unique fingerprint.

Cite this