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; 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

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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer review

2 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Pagina's (van-tot)	62-68
Aantal pagina's	7
Tijdschrift	Operations Research Letters
Volume	49
Nummer van het tijdschrift	1
DOI's	https://doi.org/10.1016/j.orl.2020.11.005
Status	Gepubliceerd - jan. 2021

Toegang tot document

10.1016/j.orl.2020.11.005Licentie: CC BY

Andere bestanden en links

Link to publication in Scopus

Citeer dit

@article{f976d86231cd43abb01334c9580b76d3,

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\}, \{Koen M.J.\} and B.V. Halld{\'o}rsson and Halld{\'o}rsson, \{Magn{\'u}s M.\} and Hurkens, \{Cor A.J.\} and J.K. Lenstra and R. Ravi and L. Stougie",

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: a performance analysis based on linear programming

AU - De Bontridder, Koen M.J.

AU - Halldórsson, B.V.

AU - Halldórsson, Magnús M.

AU - Hurkens, Cor 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

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

Samenvatting

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit