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

K. M.J. De Bontridder; Bjarni Vilhjálmur Halldórsson; Magnús Már Halldórsson; C. A.J. Hurkens; J. K. Lenstra; R. Ravi; L. Stougie

doi:10.1016/j.orl.2020.11.005

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

K. M.J. De Bontridder, Bjarni Vilhjálmur Halldórsson, Magnús Már Halldórsson, C. A.J. Hurkens, J. K. Lenstra, R. Ravi, L. Stougie

Reykjavik University

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	62-68
Number of pages	7
Journal	Operations Research Letters
Volume	49
Issue number	1
DOIs	https://doi.org/10.1016/j.orl.2020.11.005
Publication status	Published - Jan 2021

Bibliographical note

Other keywords

Greedy algorithm
Linear programming
Local search
Path packing
Performance guarantee

Access to Document

10.1016/j.orl.2020.11.005

Cite this

@article{43ac3869392a42628ba13fc1d6b28f17,

title = "Local improvement algorithms for a path packing problem: A performance analysis based on linear programming",

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.",

keywords = "Greedy algorithm, Linear programming, Local search, Path packing, Performance guarantee",

author = "\{De Bontridder\}, \{K. M.J.\} and Halld{\'o}rsson, \{Bjarni Vilhj{\'a}lmur\} and Halld{\'o}rsson, \{Magn{\'u}s M{\'a}r\} and Hurkens, \{C. A.J.\} and Lenstra, \{J. K.\} and R. Ravi and L. Stougie",

note = "Funding Information: We are grateful for the comments of the area editor and the referees, which helped us to improve the presentation. Publisher Copyright: {\textcopyright} 2020 The Authors",

year = "2021",

month = jan,

doi = "10.1016/j.orl.2020.11.005",

language = "English",

volume = "49",

pages = "62--68",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Local improvement algorithms for a path packing problem

T2 - A performance analysis based on linear programming

AU - De Bontridder, K. M.J.

AU - Halldórsson, Bjarni Vilhjálmur

AU - Halldórsson, Magnús Már

AU - Hurkens, C. A.J.

AU - Lenstra, J. K.

AU - Ravi, R.

AU - Stougie, L.

PY - 2021/1

Y1 - 2021/1

N2 - 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.

AB - 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.

KW - Greedy algorithm

KW - Linear programming

KW - Local search

KW - Path packing

KW - Performance guarantee

UR - https://www.scopus.com/pages/publications/85096647535

UR - https://iris.ru.is/ws/files/40328488/1_s2.0_S0167637720301723_main.pdf

U2 - 10.1016/j.orl.2020.11.005

DO - 10.1016/j.orl.2020.11.005

M3 - Article

SN - 0167-6377

VL - 49

SP - 62

EP - 68

JO - Operations Research Letters

JF - Operations Research Letters

IS - 1

ER -

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

Abstract

Bibliographical note

Other keywords

Access to Document

Fingerprint

Cite this