Approximation algorithms for the maximum-weight cycle/path packing problems

DOI10.1142/S0217595923400031MaRDI QIDQ6542868zbMATH OpenFDO

Authors Shiming Li, Wei Yu

Publication date 23 May 2024

Published in Asia-Pacific Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0217595923400031

zbMATH Keywords

approximation algorithmcycle packingpath packingtriangle inequality

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximation algorithms for cycle packing problems
• Algorithms – ESA 2004
• An approximation algorithm for maximum triangle packing
• Improved approximation algorithms for weighted 2-path partitions

Cites work

• A 4/5 -- approximation algorithm for the maximum traveling salesman problem
• A randomized approximation algorithm for metric triangle packing
• An approximation algorithm for maximum packing of 3-edge paths
• An approximation algorithm for maximum triangle packing
• An improved randomized approximation algorithm for maximum triangle packing
• Approximations for maximum transportation with permutable supply vector and other capacitated star packing problems
• Combinatorial optimization. Theory and algorithms
• Deterministic 7/8-approximation for the metric maximum TSP
• Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems
• Erratum to ``An approximation algorithm for maximum triangle packing
• Erratum to: ``An improved randomized approximation algorithm for maximum triangle packing
• scientific article; zbMATH DE number 1617260 (Why is no real title available?)
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 5999574 (Why is no real title available?)
• Improved approximation algorithms for weighted 2-path partitions
• Local search algorithms for the maximum carpool matching problem
• Maximum weight cycle packing in directed graphs, with application to kidney exchange programs
• On local search for weighted \(k\)-set packing
• On the completeness of a generalized matching problem
• On the maximum quadratic assignment problem
• The limits of local search for weighted \(k\)-set packing

Cited in

(6)

• Improved approximation algorithms for cycle and path packings
• A deterministic approximation algorithm for metric triangle packing
• An improved approximation algorithm for metric triangle packing
• Approximating the maximum weight cycle/path partition in graphs with weights one and two
• Approximating the maximum weight cycle/path partition in graphs with weights one and two
• Approximation algorithms for cycle and path partitions in complete graphs

This page was built for publication: Approximation algorithms for the maximum-weight cycle/path packing problems

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