摘要:
在树上k-奖励收集多割问题中，给定一个无向树T=(V,E)，一个由m个结点对构成的集合P
= {(
s1 ,
t1 )
, (
s2 ,
t2 ),..., (
sm ,
tm )}和一个参数k且k≤m。E中的每一条边都有一个非负成本c
e，P中的每一个结点对都有一个非负惩罚成本π
i。目标是求一个能分离P中至少k个结点对的多割M，使得多割M中边的成本与未被M分割的结点对的惩罚成本之和最小。这个问题是著名的树上的多割问题的推广。在本文中，我们设计了一个树上k-奖励收集多割问题的近似比为
的近似算法，其中ε是任意一个确定的正数。
Abstract:
In the k-prize-collecting multicut on a tree (k-PCM(T)) problem, we give an undirected tree
T=(V,E), a set of m distinct pairs of vertices
P = {(s1 , t1 ), ( s2 , t2 ),..., ( sm , tm )} and a parameter k with
k≤m. Every edge in E has a nonnegative cost
ce. Every pair
(s1 , t1 ) in P has a nonnegative penalty cost
π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. In this paper, we design an approximation algorithm for the k-PCM(T) problem with approximation ratio
, where is a fixed number.