Name
Abstract | ||
|---|---|---|
In this paper, we consider the k-prize-collecting multicut on a tree (k-PCM(T)) problem. In this problem, we are given an undirected tree T = (V, E), a set of m distinct pairs of vertices P = {(s(1), t(1)), . . . , (s(m), t(m))} and a parameter k with k <= m. Every edge in E has a nonnegative cost c(e). Every pair (s(i), t(i)) in P has a nonnegative penalty cost pi(i). Our goal is to find a multicut M that separates at least k pairs in P such that the total cost, including the edge cost of the multicut M and the penalty cost of the pairs not separated by M, is minimized. This problem generalizes the well-known multicut on a tree problem. Our main work is to present a (4 + epsilon)-approximation algorithm for the k-PCM(T) problem via the methods of primal-dual and Lagrangean relaxation, where s is any fixed positive number. (C) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1016/j.tcs.2020.07.014 | THEORETICAL COMPUTER SCIENCE |
Keywords | DocType | Volume |
Multicut,k-prize-collecting multicut,Approximation algorithm,Primal-dual algorithm,Lagrange relaxation | Journal | 844 |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.36 |
References | Authors | |
0 | 3 | |