Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties

DOI10.1007/s10878-020-00568-2zbMath1502.90154OpenAlexW3015650256MaRDI QIDQ2082211

Weidong Li, Xiaofei Liu

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00568-2

zbMATH Keywords

approximation algorithmprimal-dualmulticutsubmodular penalties

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique
• An approximation algorithm for the generalized \(k\)-multicut problem
• Primal-dual approximation algorithms for integral flow and multicut in trees
• A note on the submodular vertex cover problem with submodular penalties
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Partial multicuts in trees
• Improved parameterized and exact algorithms for cut problems on trees
• A primal-dual approximation algorithm for the facility location problem with submodular penalties
• On the generalized multiway cut in trees problem
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Submodular functions and optimization.
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• The Complexity of Multiterminal Cuts
• Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
• Submodular Function Minimization under Covering Constraints