caa a22 4500 445804955 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110401xx s 000 0 eng 10.1007/s00453-009-9316-1 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9316-1 Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k -Way Cut Problem [Elektronische Daten] [Mingyu Xiao, Leizhen Cai, Andrew Yao] For an edge-weighted connected undirected graph, the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. The problem is NP-hard when k is part of the input and W[1]-hard when k is taken as a parameter. A simple algorithm for approximating a minimum k-way cut is to iteratively increase the number of components of the graph by h−1, where 2≤h≤k, until the graph has k components. The approximation ratio of this algorithm is known for h≤3 but is open for h≥4. In this paper, we consider a general algorithm that successively increases the number of components of the graph by h i−1, where 2≤h 1≤h 2≤⋅⋅⋅≤h q and ∑i=1q(h i−1)=k−1. We prove that the approximation ratio of this general algorithm is $2-(\sum_{i=1}^{q}{h_{i}\choose2})/{k\choose2}$ , which is tight. Our result implies that the approximation ratio of the simple iterative algorithm is 2−h/k+O(h 2/k 2) in general and 2−h/k if k−1 is a multiple of h−1. Springer Science+Business Media, LLC, 2009 k -way cut nationallicence Approximation algorithm nationallicence Xiao Mingyu School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, China aut Cai Leizhen Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR, China aut Yao Andrew Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR, China aut Algorithmica Springer-Verlag 59/4(2011-04-01), 510-520 0178-4617 59:4<510 2011 59 453 https://doi.org/10.1007/s00453-009-9316-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9316-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Xiao Mingyu School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, China aut NATIONALLICENCE 700 1- Cai Leizhen Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR, China aut NATIONALLICENCE 700 1- Yao Andrew Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR, China aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/4(2011-04-01), 510-520 0178-4617 59:4<510 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer