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

An Zhang; Bing Su; Guohui Lin; Longcheng Liu; Randy Goebel; Weitian Tong; Yao Xu; Yong Chen

REVIEW

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1812.09353 v1 pith:RLW2O4NC submitted 2018-12-21 cs.DS

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

Yong Chen , Randy Goebel , Guohui Lin , Longcheng Liu , Bing Su , Weitian Tong , Yao Xu , An Zhang This is my paper

classification cs.DS

keywords problemapproximationalgorithmcoverpartitionpathratiobest

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

0 comments

read the original abstract

Given a graph $G = (V, E)$, the $3$-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most $3$ to cover all the vertices of $V$. It is different from but closely related to the well-known $3$-set cover problem. The best known approximation algorithm for the $3$-path partition problem was proposed recently and has a ratio $13/9$. Here we present a local search algorithm and show, by an amortized analysis, that it is a $4/3$-approximation. This ratio matches up to the best approximation ratio for the $3$-set cover problem.

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

discussion (0)