A Primal Dual Approximation Algorithm for the Multicut Problem in Trees with Submodular Penalties

被引：3
作者：
Liu, Xiaofei [1 ]
Li, Weidong [2 ,3 ]
机构：
[1] Peking Univ, Sch Elect Engn & Comp Sci, Beijing 100871, Peoples R China
[2] Yunnan Univ, Sch Math & Stat, Kunming 650504, Yunnan, Peoples R China
[3] Yunnan Univ, Dianchi Coll, Kunming 650000, Yunnan, Peoples R China
来源：
ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019 | 2019年 / 11640卷
基金：
中国国家自然科学基金;
关键词：
Multicut; Submodular functions; Approximation algorithm; CUT;
D O I：
10.1007/978-3-030-27195-4_19
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we introduce the multicut problem in trees with submodular penalties, which generalizes the prize-collecting multicut problem in trees and vertex cover with submodular penalties. We present a combinatorial 3-approximation algorithm, based on the primal-dual scheme for the multicut problem in trees.
引用
收藏
页码：203 / 211
页数：9
相关论文
共 17 条
[1]   THE COMPLEXITY OF MULTITERMINAL CUTS [J].
DAHLHAUS, E ;
JOHNSON, DS ;
PAPADIMITRIOOU, CH ;
SEYMOUR, PD ;
YANNAKAKIS, M .
SIAM JOURNAL ON COMPUTING, 1994, 23 (04) :864-894
[2]   A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties [J].
Du, Donglei ;
Lu, Ruixing ;
Xu, Dachuan .
ALGORITHMICA, 2012, 63 (1-2) :191-200
[3]  
Fujishige S, 2005, ANN DISCR MATH, V58, P1
[4]   Approximate max-flow min-(multi)cut theorems and their applications [J].
Garg, N ;
Vazirani, VV ;
Yannakakis, M .
SIAM JOURNAL ON COMPUTING, 1996, 25 (02) :235-251
[5]   Primal-dual approximation algorithms for integral flow and multicut in trees [J].
Garg, N ;
Vazirani, VV ;
Yannakakis, M .
ALGORITHMICA, 1997, 18 (01) :3-20
[6]  
Hayrapetyan A, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P933
[7]  
Hu T.C., 1969, Integer programming and network ows
[8]   A combinatorial strongly polynomial algorithm for minimizing submodular functions [J].
Iwata, S ;
Fleischer, L ;
Fujishige, S .
JOURNAL OF THE ACM, 2001, 48 (04) :761-777
[9]   Submodular Function Minimization under Covering Constraints [J].
Iwata, Satoru ;
Nagano, Kiyohito .
2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :671-680
[10]   A note on the submodular vertex cover problem with submodular penalties [J].
Kamiyama, Naoyuki .
THEORETICAL COMPUTER SCIENCE, 2017, 659 :95-97
12