A 21/16-Approximation for the Minimum 3-Path Partition Problem

DOI10.4230/LIPIcs.ISAAC.2019.46OpenAlexW2990814010MaRDI QIDQ5875609

Randy Goebel, Yao Xu, Bing Su, Weitian Tong, Yong Chen, An Zhang

Publication date: 3 February 2023

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2019/11542/pdf/LIPIcs-ISAAC-2019-46.pdf/

zbMATH Keywords

approximation algorithmlocal searchamortized analysisexact set cover\(3\)-path partition

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (4)

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 21/16-Approximation for the Minimum 3-Path Partition Problem