A local search algorithm for the k-path partition problem

DOI10.1007/S11590-023-01989-8MaRDI QIDQ6181375zbMATH OpenOpenAlexFDO

Authors Shiming Li, Wei Yu, Zhaohui Liu

Publication date 22 January 2024

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-023-01989-8

zbMATH Keywords

approximation algorithmlocal searchpath partitionset covering

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Recommendations

• Improved approximation algorithms for the \(k\)-path partition problem
• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• Approximation algorithms for the directed path partition problems
• An improved approximation algorithm for the minimum 3-path partition problem

Cites work

• \(k\)-path partitions in trees
• A 21/16-Approximation for the Minimum 3-Path Partition Problem
• A boundary class for the k-path partition problem
• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• An improved approximation algorithm for the minimum 3-path partition problem
• Approximating the Unweighted ${k}$-Set Cover Problem: Greedy Meets Local Search
• Approximation algorithms for the directed path partition problems
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• Maximum skew-symmetric flows and matchings
• On the \(k\)-path partition of graphs.
• On the k-path partition problem in cographs
• On the completeness of a generalized matching problem
• The path partition problem and related problems in bipartite graphs

Cited in

(10)

• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• Local improvement algorithms for a path packing problem: a performance analysis based on linear programming
• Approximation algorithms for the directed path partition problems
• Improved approximation algorithms for the \(k\)-path partition problem
• Parameterizing path partitions
• An improved approximation algorithm for the minimum k-star partition problem
• Path cover using only short paths
• An improved approximation algorithm for the minimum 4-star partition problem
• Approximately partitioning vertices into short paths
• TermiNet: a reinforcement learning framework for k-path partitioning problem

This page was built for publication: A local search algorithm for the \(k\)-path partition problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6181375)