A local search 4/3-approximation algorithm for the minimum 3-path partition problem
type: Item
instance of: scholarly article
title: A local search 4/3-approximation algorithm for the minimum 3-path partition problem
zbMATH Open document ID: 1505.90099
author: Yong Chen
author: Randy Goebel
author: Longcheng Liu
author: Bing Su
author: Weitian Tong
author: Yao Xu
author: An Zhang
author: Guohui Lin
published in: Journal of Combinatorial Optimization
publication date: 2022-10-31T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 7610143
zbMATH Keywords: path partition
zbMATH Keywords: path cover
zbMATH Keywords: local search
zbMATH Keywords: approximation algorithms
zbMATH Keywords: amortized analysis
MaRDI profile type: Publication
full work available at URL: s10878-022-00915-5
OpenAlex ID: W2952981837
cites work: A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
cites work: An improved approximation algorithm for the minimum 3-path partition problem
cites work: A 21/16-Approximation for the Minimum 3-Path Partition Problem
cites work: Q4526990
cites work: A threshold of ln n for approximating set cover
cites work: Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
cites work: Q4198056
cites work: Maximum skew-symmetric flows and matchings
cites work: Approximation algorithms for combinatorial problems
cites work: Reducibility among Combinatorial Problems
cites work: Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search
cites work: The path partition problem and related problems in bipartite graphs
cites work: Q4527015
cites work: \(k\)-path partitions in trees
DOI: 10.1007/S10878-022-00915-5
description: scientific article; zbMATH DE number 7610143