Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477091 | European Journal of Operational Research | 2010 | 8 Pages |
Abstract
Given a complete graph G=(V,E)G=(V,E), a weight function w:E→N0w:E→N0 on its edges, and p→N0p→N0 a penalty function on its vertices, the penalizedk-min-sum problem is the problem of finding a partition of V to k+1k+1 sets, S1,…,Sk+1S1,…,Sk+1, minimizing ∑i=1kw(Si)+p(Sk+1), where for S⊆Vw(S)=∑e={i,j}⊆Swe, and p(S)=∑i∈Spip(S)=∑i∈Spi.Our main result is a randomized approximation scheme for the metric version of the penalized 1-min-sum problem, when the ratio between the minimal and maximal penalty is bounded. For the metric penalized k-min-sum problem where k is a constant, we offer a 2-approximation.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Refael Hassin, Einat Or,