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

被引：2

作者：

De Bontridder, K. M. J. ^{[1
]}

Halldorsson, B. V. ^{[2
,3
]}

Halldorsson, M. M. ^{[3
]}

Hurkens, C. A. J. ^{[4
]}

Lenstra, J. K. ^{[5
]}

Ravi, R. ^{[6
]}

Stougie, L. ^{[5
]}

机构：

[1] Mapscape Bv, Eindhoven, Netherlands

[2] deCODE Genet, Reykjavik, Iceland

[3] Reykjavik Univ, Reykjavik, Iceland

[4] Eindhoven Univ Technol, Eindhoven, Netherlands

[5] Ctr Wiskunde & Informat, Amsterdam, Netherlands

[6] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA

来源：

OPERATIONS RESEARCH LETTERS | 2021年 / 49卷 / 01期

关键词：

Path packing; Greedy algorithm; Local search; Performance guarantee; Linear programming; APPROXIMATION ALGORITHM;

D O I：

10.1016/j.orl.2020.11.005

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (c) 2020 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

引用

页码：62 / 68

页数：7

共 7 条

[1] Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
Bafna, V
Narayanan, B
Ravi, R
[J]. DISCRETE APPLIED MATHEMATICS, 1996, 71 (1-3) : 41 - 53
[2] Approximation algorithms for the test cover problem
De Bontridder, KMJ
Halldórsson, BV
Halldórsson, MM
Hurkens, CAJ
Lenstra, JK
Ravi, R
Stougie, L
[J]. MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) : 477 - 491
[3] A parameterized perspective on packing paths of length two
Fernau, Henning
Raible, Daniel
[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (04) : 319 - 341
[4] An approximation algorithm for maximum triangle packing
Hassin, R
Rubinstein, S
[J]. DISCRETE APPLIED MATHEMATICS, 2006, 154 (06) : 971 - 979
[5] An approximation algorithm for maximum packing of 3-edge paths
Hassin, R
Rubinstein, S
[J]. INFORMATION PROCESSING LETTERS, 1997, 63 (02) : 63 - 67
[6] Hurkens C.A.J., 1989, SIAM J. Disc. Math., V2, P68, DOI DOI 10.1137/0402008
[7] Kirkpatrick D. G., 1978, P 10 ANN ACM S THEOR, P240

← 1 →