Anzeige
Erschienen in:
01.01.2019
An improved approximation algorithm for the minimum 3-path partition problem
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2019
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Given a graph \(G = (V, E)\), we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the well-known path cover problem and the set cover problem. The general k-path partition problem for a constant \(k \ge 3\) is NP-hard, and it admits a trivial k-approximation. When \(k = 3\), the previous best approximation ratio is 1.5 due to Monnot and Toulouse (Oper Res Lett 35:677–684, 2007), based on two maximum matchings. In this paper we first show how to compute in polynomial time a 3-path partition with the least 1-paths, and then apply a greedy approach to merge three 2-paths into two 3-paths whenever possible. Through an amortized analysis, we prove that the proposed algorithm is a 13 / 9-approximation. We also show that the performance ratio 13 / 9 is tight for our algorithm.