A primal dual approximation algorithm for the multicut problem in trees with submodular penalties

DOI10.1007/978-3-030-27195-4_19MaRDI QIDQ6199016zbMATH OpenOpenAlexFDO

Authors Xiaofei Liu, Weidong Li

Publication date 23 February 2024

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-27195-4_19

zbMATH Keywords

approximation algorithmmulticutsubmodular functions

Mathematics Subject Classification ID

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• 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
• Approximation algorithms for prize collecting forest problems with submodular penalty functions
• An approximation algorithm for the generalized prize-collecting Steiner forest problem with submodular penalties
• Approximating Generalized Multicut on Trees

This page was built for publication: A primal dual approximation algorithm for the multicut problem in trees with submodular penalties

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