An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees

DOI10.1007/978-3-031-20350-3_21MaRDI QIDQ6111962

Xiaofei Liu, Weidong Li

Publication date: 4 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmprimal-dual scheme\(B\)-prize-collectingmulticut problem in trees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• An approximation algorithm for the generalized \(k\)-multicut problem
• A unified approach to approximating partial covering problems
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Partial multicuts in trees
• Exact algorithms and applications for tree-like Weighted Set Cover
• A primal-dual approximation algorithm for the \(k\)-prize-collecting minimum power cover problem
• Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties
• An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem
• A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• An approximation algorithm for \(P\)-prize-collecting set cover problem
• Parameterized complexity of weighted multicut in trees

This page was built for publication: An approximation algorithm for the \(B\)-prize-collecting multicut problem in trees