Approximation Algorithms for Minimum K -Cut |
| |
Authors: | N Guttmann-Beck R Hassin |
| |
Affiliation: | (1) Department of Statistics and Operations Research, Tel Aviv University, Tel Aviv 69978, Israel. nili@math.tau.ac.il, hassin@math.tau.ac.il. , IL |
| |
Abstract: | Let G=(V,E) be a complete undirected graph, with node set V={v
1
, . . ., v
n
} and edge set E . The edges (v
i
,v
j
) ∈ E have nonnegative weights that satisfy the triangle inequality. Given a set of integers K = { k
i
}
i=1
p
, the minimum K-cut problem is to compute disjoint subsets with sizes { k
i
}
i=1
p
, minimizing the total weight of edges whose two ends are in different subsets. We demonstrate that for any fixed p it is possible to obtain in polynomial time an approximation of at most three times the optimal value. We also prove bounds
on the ratio between the weights of maximum and minimum cuts.
Received September 4, 1997; revised July 15, 1998. |
| |
Keywords: | , Approximation algorithms, Minimum cuts, |
本文献已被 SpringerLink 等数据库收录! |
|