کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477715 | 1446179 | 2008 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Approximating k-cuts using network strength as a Lagrangean relaxation Approximating k-cuts using network strength as a Lagrangean relaxation](/preview/png/477715.png)
Given an undirected, edge-weighted connected graph, the k-cut problem is to partition the vertex set into k non-empty connected components so as to minimize the total weight of edges whose end points are in different components.We present a combinatorial polynomial-time 2-approximation algorithm for the k-cut problem. We use a Lagrangean relaxation (also suggested by Barahona [F. Barahona, On the k-cut problem, Operations Research Letters 26 (2000) 99–105]) to reduce the problem to the attack problem, for which a polynomial time algorithm was provided by Cunningham [W. Cunningham, Optimal attack and reinforcement of a network, Journal of the ACM 32(3) (1985) 549–561]. We prove several structural results of the relaxation, and use these results to develop an approximation algorithm.We provide analytical comparisons of our algorithm and lower bound with two others: Saran and Vazirani [H. Saran, V. Vazirani, Finding k-cuts within twice the optimal, SIAM Journal of Computing 24(1) (1995) 101–108] and Naor and Rabani [J. Naor, Y. Rabani, Tree packing and approximating k-cuts. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, 2001, pp. 26–27]. We also provide computational results comparing the performance of our algorithm on random graphs with respect to the lower bound provided by the attack problem as well as an alternate 2-approximation algorithm provided by Saran and Vazirani [Cited above].
Journal: European Journal of Operational Research - Volume 186, Issue 1, 1 April 2008, Pages 77–90