2026-08-18T07:54:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11542 2024-03-06T10:48:16Z ddc:004 open_access

A 21/16-Approximation for the Minimum 3-Path Partition Problem Chen, Yong Goebel, Randy Su, Bing Tong, Weitian Xu, Yao Zhang, An 3-path partition exact set cover approximation algorithm local search amortized analysis 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 l-paths, l in {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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yong Chen and Randy Goebel and Bing Su and Weitian Tong and Yao Xu and An Zhang 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.46 urn:nbn:de:0030-drops-115422 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.46 eng https://creativecommons.org/licenses/by/3.0/legalcode