An approximation algorithm for the submodular multicut problem in trees with linear penalties
- PDF / 231,893 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 40 Downloads / 207 Views
An approximation algorithm for the submodular multicut problem in trees with linear penalties Chenfei Hou1 · Suogang Gao1 · Wen Liu1 · Weili Wu2 · Ding-Zhu Du2 · Bo Hou1 Received: 11 August 2020 / Accepted: 4 November 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we consider the submodular multicut problem in trees with linear penalties (SMCLP(T ) problem). In the SMCLP(T ) problem, we are given a tree T = (V , E) with a submodular function c(·) : 2 E → R≥0 , a set of k distinct pairs of vertices P = {(s1 , t1 ), (s2 , t2 ), . . . , (sk , tk )} with non-negative penalty costs π j for the pairs (s j , t j ) ∈ P. The goal is to find a partial multicut M ⊆ E such that the total cost, consisting of the submodular cost of M and the penalty cost of the pairs not cut by M, is minimized. Let P j be the unique path from s j to t j in the tree, where 1 ≤ j ≤ k and let m be the maximal length of all P j . Our main work is to present an m-approximation algorithm for the SMCLP(T ) problem via the primal-dual method. Keywords Multicut · Submodular function · Primal-dual algorithm
1 Introduction The main focus of this paper is the submodular multicut problem in trees with linear penalties (SMCLP(T ) problem). To state this problem, we first recall some related concepts. For a given finite set U , a set function f : 2U → R≥0 is called submodular, if f (X ∪ Y ) + f (X ∩ Y ) ≤ f (X ) + f (Y ) for any X , Y ∈ 2U . A submodular function is called modular if the equality holds. Let G = (V , E) be an undirected graph with a set of k distinct pairs of vertices P = {(s1 , t1 ), (s2 , t2 ), . . . , (sk , tk )}. Let M be a subset of E. For 1 ≤ j ≤ k, the pair (s j , t j ) is said to be cut by M if s j and t j are
B
Bo Hou [email protected]
1
School of Mathematical Sciences, Hebei Normal University, Shijiazhuang 050024, People’s Republic of China
2
Department of Computer Science, University of Texas at Dallas, Richardson, TX 75080, USA
123
C. Hou et al.
not contained in a single connected component of G\M. The set M is called a partial multicut if some pairs in P are cut by M. In the SMCLP(T ) problem, we are given a tree T = (V , E) with a submodular function c(·) : 2 E → R≥0 , a set of k distinct pairs of vertices P = {(s1 , t1 ), (s2 , t2 ), · · · , (sk , tk )} with non-negative penalty costs π j for the pairs (s j , t j ) ∈ P. The goal is to find a partial multicut M ⊆ E such that the total cost, consisting of the submodular cost of M and the penalty cost of the pairs not cut by M, is minimized. The SMCLP(T ) problem can be seen as a generalization of the multicut problem in trees and the prize-collecting multicut problem in trees. If the cost function c(·) is linear and the penalty cost π j = ∞ for each pair (s j , t j ) ∈ P, then the SMCLP(T ) problem is exactly the multicut problem in trees. For the multicut problem in trees, Garg et al. [1] presented a 2-approximation algorithm by using the primal-dual method. If the cost function c(·) is linear, then the SMCLP(T ) problem is ex
Data Loading...
