A local search 4/3-approximation algorithm for the minimum 3-path partition problem

Yong Chen; Randy Goebel; Guohui Lin; Longcheng Liu; Bing Su; Weitian Tong; Yao Xu; An Zhang

doi:10.1007/s10878-022-00915-5

A local search 4/3-approximation algorithm for the minimum 3-path partition problem

Yong Chen, Randy Goebel, Guohui Lin, Longcheng Liu, Bing Su, Weitian Tong, Yao Xu, An Zhang

Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

Given a graph G= (V, E) , the 3-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most 3 to cover all the vertices of V. The previous best approximation algorithm for the 3-path partition problem has a performance ratio 13/9, which is based on a simple local search strategy. We propose a more involved local search and show by an amortized analysis that it is a 4/3-approximation; we also design an instance to illustrate that the approximation ratio is tight.

Original language	English
Article number	5
Pages (from-to)	3595-3610
Number of pages	16
Journal	Journal of Combinatorial Optimization
Volume	44
Issue number	5
DOIs	https://doi.org/10.1007/s10878-022-00915-5
State	Published - Sep 28 2022

Scopus Subject Areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

Keywords

Amortized analysis
Approximation algorithms
Local search
Path cover
Path partition

Access to Document

10.1007/s10878-022-00915-5

Cite this

@article{4d3e7cd9f16942f0b2fe67aefc8681a0,

title = "A local search 4/3-approximation algorithm for the minimum 3-path partition problem",

abstract = "Given a graph G= (V, E) , the 3-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most 3 to cover all the vertices of V. The previous best approximation algorithm for the 3-path partition problem has a performance ratio 13/9, which is based on a simple local search strategy. We propose a more involved local search and show by an amortized analysis that it is a 4/3-approximation; we also design an instance to illustrate that the approximation ratio is tight.",

keywords = "Amortized analysis, Approximation algorithms, Local search, Path cover, Path partition",

author = "Yong Chen and Randy Goebel and Guohui Lin and Longcheng Liu and Bing Su and Weitian Tong and Yao Xu and An Zhang",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2022",

month = sep,

day = "28",

doi = "10.1007/s10878-022-00915-5",

language = "English",

volume = "44",

pages = "3595--3610",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "5",

}

TY - JOUR

T1 - A local search 4/3-approximation algorithm for the minimum 3-path partition problem

AU - Chen, Yong

AU - Goebel, Randy

AU - Lin, Guohui

AU - Liu, Longcheng

AU - Su, Bing

AU - Tong, Weitian

AU - Xu, Yao

AU - Zhang, An

PY - 2022/9/28

Y1 - 2022/9/28

N2 - Given a graph G= (V, E) , the 3-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most 3 to cover all the vertices of V. The previous best approximation algorithm for the 3-path partition problem has a performance ratio 13/9, which is based on a simple local search strategy. We propose a more involved local search and show by an amortized analysis that it is a 4/3-approximation; we also design an instance to illustrate that the approximation ratio is tight.

AB - Given a graph G= (V, E) , the 3-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most 3 to cover all the vertices of V. The previous best approximation algorithm for the 3-path partition problem has a performance ratio 13/9, which is based on a simple local search strategy. We propose a more involved local search and show by an amortized analysis that it is a 4/3-approximation; we also design an instance to illustrate that the approximation ratio is tight.

KW - Amortized analysis

KW - Approximation algorithms

KW - Local search

KW - Path cover

KW - Path partition

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

U2 - 10.1007/s10878-022-00915-5

DO - 10.1007/s10878-022-00915-5

M3 - Article

AN - SCOPUS:85139259007

SN - 1382-6905

VL - 44

SP - 3595

EP - 3610

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 5

M1 - 5

ER -

A local search 4/3-approximation algorithm for the minimum 3-path partition problem

Abstract

Scopus Subject Areas

Keywords

Access to Document

Other files and links

Fingerprint

Cite this