| Title | Combinatorial approximation algorithms for the submodular multicut problem in trees with submodular penalties |
| Authors | Liu, Xiaofei Li, Weidong |
| Affiliation | Peking Univ, Sch Elect Engn & Comp Sci, Beijing 100871, Peoples R China Yunnan Univ, Sch Math & Stat, Kunming 650504, Yunnan, Peoples R China |
| Keywords | FLOW CUT |
| Issue Date | Apr-2020 |
| Publisher | JOURNAL OF COMBINATORIAL OPTIMIZATION |
| Abstract | In this paper, we introduce the submodular multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and the submodular vertex cover with submodular penalties. We present a combinatorial approximation algorithm, based on the primal-dual algorithm for the submodular set cover problem. In addition, we present a combinatorial 3-approximation algorithm for a special case where the edge cost is a modular function, based on the primal-dual scheme for the multicut problem in trees. |
| URI | http://hdl.handle.net/20.500.11897/606632 |
| ISSN | 1382-6905 |
| DOI | 10.1007/s10878-020-00568-2 |
| Indexed | SCI(E) Scopus EI |
| Appears in Collections: | 信息科学技术学院 |
