Optimal 3-terminal cuts and linear programming

• 成果类型: Article
• 署名作者: Cheung, KKH; Cunningham, WH; Tang, L
• 署名单位: Carleton University; University of Waterloo; Hong Kong Monetary Authority (HKMA)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0668-2
• 发表日期: 2006
• 页码: 1-23
• 关键词: multiway cut

摘要

Given an undirected graph G = (V, E) and three specified terminal nodes t(1), t(2), t(3), a 3-cut is a subset A of E such that no two terminals are in the same component of G\A. If a non-negative edge weight c(e) is specified for each e. E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is NP-hard, and in fact, is max-SNP-hard. An approximation algorithm having performance guarantee 7/6 has recently been given by Calinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most 7/6 times the optimal LP value. It is proved here that 7/6 can be improved to 12 /11, and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee 12/11. In addition, we show that 12/11 is best possible for this algorithm.