An improved approximation algorithm for the minimum 3-path partition problem
Full Text: Chen2019_Article_AnImprovedApproximationAlgorit.pdf
Given a graph 𝐺=(𝑉,𝐸) , we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the well-known path cover problem and the set cover problem. The general k-path partition problem for a constant 𝑘≥3 is NP-hard, and it admits a trivial k-approximation. When 𝑘=3 , the previous best approximation ratio is 1.5 due to Monnot and Toulouse (Oper Res Lett 35:677–684, 2007), based on two maximum matchings. In this paper we first show how to compute in polynomial time a 3-path partition with the least 1-paths, and then apply a greedy approach to merge three 2-paths into two 3-paths whenever possible. Through an amortized analysis, we prove that the proposed algorithm is a 13 / 9-approximation. We also show that the performance ratio 13 / 9 is tight for our algorithm.
Citation
Y. Chen, R. Goebel, G. Lin, B. Su, Y. Xu, A. Zhang. "An improved approximation algorithm for the minimum 3-path partition problem". Journal of Combinational Optimization, 38(1), pp 150-164, July 2019.| Keywords: | k-Path partition Path cover, k-Set cover , Approximation algorithm, Amortized analysis |
| Category: | In Journal |
| Web Links: | DOI |
| Springer |
BibTeX
@article{Chen+al:19,
author = {Yong Chen and Randy Goebel and Guohui Lin and Bing Su and Yao Xu
and An Zhang},
title = {An improved approximation algorithm for the minimum 3-path partition
problem},
Volume = "38",
Number = "1",
Pages = {150-164},
journal = {Journal of Combinational Optimization},
year = 2019,
}Last Updated: February 13, 2020Submitted by Sabina P
