@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",
}