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

DOI10.1007/978-3-030-18126-0_2OpenAlexW2905953446MaRDI QIDQ2327083

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

Publication date: 11 October 2019

Full work available at URL: https://arxiv.org/abs/1812.09353

zbMATH Keywords

local searchapproximation algorithmspath cover\(k\)-set coveramortized analysis\(k\)-path partition

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (6)

Path cover problems with length cost ⋮ Approximation algorithms for the directed path partition problems ⋮ A local search algorithm for the \(k\)-path partition problem ⋮ Approximating the directed path partition problem ⋮ Path cover problems with length cost ⋮ A local search 4/3-approximation algorithm for the minimum 3-path partition problem

This page was built for publication: A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem