A 21/16-approximation for the minimum 3-path partition problem
Full Text: LIPIcs-ISAAC-2019-46.pdf
The minimum k-path partition (Min-k-PP for short) problem targets to partition an input graph into the smallest number of paths, each of which has order at most k. We focus on the special case when k = 3. Existing literature mainly concentrates on the exact algorithms for special graphs, such as trees. Because of the challenge of NP-hardness on general graphs, the approximability of the Min-3-PP problem attracts researchers’ attention. The first approximation algorithm dates back about 10 years and achieves an approximation ratio of 3 2 , which was recently improved to 13 9 and further to 4 3 . We investigate the 3 2 -approximation algorithm for the Min-3-PP problem and discover several interesting structural properties. Instead of studying the unweighted Min-3-PP problem directly, we design a novel weight schema for `-paths, ` ∈ {1, 2, 3}, and investigate the weighted version. A greedy local search algorithm is proposed to generate a heavy path partition. We show the achieved path partition has the least 1-paths, which is also the key ingredient for the algorithms with ratios 13 9 and 4 3 . When switching back to the unweighted objective function, we prove the approximation ratio 21 16 via amortized analysis.
Citation
Y. Chen, R. Goebel, B. Su, W. Tong, Y. Xu, A. Zhang. "A 21/16-approximation for the minimum 3-path partition problem". International Symposium on Algorithms and Computation (ISAAC), pp 1-20, December 2019.| Keywords: | |
| Category: | In Conference |
| Web Links: | DROPS |
BibTeX
@incollection{Chen+al:(ISAAC)19,
author = {Yong Chen and Randy Goebel and Bing Su and Weitian Tong and Yao Xu
and An Zhang},
title = {A 21/16-approximation for the minimum 3-path partition problem},
Pages = {1-20},
booktitle = { International Symposium on Algorithms and Computation (ISAAC)},
year = 2019,
}Last Updated: September 10, 2020Submitted by Sabina P
