Name
Title | ||
|---|---|---|
An Approximation Algorithm For The Submodular Multicut Problem In Trees With Linear Penalties |
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 = {(s(1), t(1)), (s(2), t(2)), ... , (s(k), t(k))} with non-negative penalty costs pi(j) for the pairs (s(j), t(j)) is an element of P. The goal is to find a partial multicut M subset of 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s11590-020-01665-1 | OPTIMIZATION LETTERS |
Keywords | DocType | Volume |
Multicut, Submodular function, Primal-dual algorithm | Journal | 15 |
Issue | ISSN | Citations |
4 | 1862-4472 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chenfei Hou | 1 | 0 | 0.34 |
| Suogang Gao | 2 | 0 | 2.03 |
| Wen Liu | 3 | 8 | 3.34 |
| Weili Wu | 4 | 2093 | 170.29 |
| Ding-Zhu Du | 5 | 6 | 1.82 |
| Bo Hou | 6 | 0 | 1.69 |