A local search 4/3-approximation algorithm for the minimum 3-path partition problem

DOI10.1007/s10878-022-00915-5zbMath1505.90099OpenAlexW2952981837MaRDI QIDQ2091113

Weitian Tong, An Zhang, Bing Su, Longcheng Liu, Randy Goebel, Yao Xu, Yong Chen, Guo-Hui Lin

Publication date: 31 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-022-00915-5

zbMATH Keywords

local searchapproximation algorithmspath coverpath partitionamortized analysis

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• \(k\)-path partitions in trees
• Maximum skew-symmetric flows and matchings
• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• An improved approximation algorithm for the minimum 3-path partition problem
• The path partition problem and related problems in bipartite graphs
• A threshold of ln n for approximating set cover
• Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
• Reducibility among Combinatorial Problems
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
• A 21/16-Approximation for the Minimum 3-Path Partition Problem