TY - GEN
T1 - A 2116-approximation for the minimum 3-path partition problem
AU - Chen, Yong
AU - Goebel, Randy
AU - Su, Bing
AU - Tong, Weitian
AU - Xu, Yao
AU - Zhang, An
N1 - Publisher Copyright:
© Yong Chen, Randy Goebel, Bing Su, Weitian Tong, Yao Xu, and An Zhang; licensed under Creative Commons License CC-BY
PY - 2019/12
Y1 - 2019/12
N2 - 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 32 , which was recently improved to 139 and further to 43 . We investigate the 32 -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 139 and 43 . When switching back to the unweighted objective function, we prove the approximation ratio 2116 via amortized analysis.
AB - 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 32 , which was recently improved to 139 and further to 43 . We investigate the 32 -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 139 and 43 . When switching back to the unweighted objective function, we prove the approximation ratio 2116 via amortized analysis.
KW - 3-path partition
KW - Amortized analysis
KW - Approximation algorithm
KW - Exact set cover
KW - Local search
UR - http://www.scopus.com/inward/record.url?scp=85076367924&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2019.46
DO - 10.4230/LIPIcs.ISAAC.2019.46
M3 - Conference article
AN - SCOPUS:85076367924
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 30th International Symposium on Algorithms and Computation, ISAAC 2019
A2 - Lu, Pinyan
A2 - Zhang, Guochuan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 30th International Symposium on Algorithms and Computation, ISAAC 2019
Y2 - 8 December 2019 through 11 December 2019
ER -