@inproceedings{d0e9f671c0824d1ab829c5ee1b4ae133,

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. It is different from but closely related to the well-known 3-set cover problem. The best known approximation algorithm for the 3-path partition problem was proposed recently and has a ratio 13/9. Here we present a local search algorithm and show, by an amortized analysis, that it is a 4/3-approximation. This ratio matches up to the best approximation ratio for the 3-set cover problem.",

keywords = "Amortized analysis, Approximation algorithms, K-path partition, K-set cover, Local search, Path cover",

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} Springer Nature Switzerland AG 2019.; 13th International Workshop on Frontiers in Algorithmics, FAW 2019 ; Conference date: 29-04-2019 Through 03-05-2019",

year = "2019",

doi = "10.1007/978-3-030-18126-0_2",

language = "English",

isbn = "9783030181253",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "14--25",

editor = "Yijia Chen and Mei Lu and Xiaotie Deng",

booktitle = "Frontiers in Algorithmics - 13th International Workshop, FAW 2019, Proceedings",

address = "Germany",

}