Greedy splitting algorithms for approximating multiway partition problems

• 成果类型: Article
• 署名作者: Zhao, L; Nagamochi, H; Ibaraki, T
• 署名单位: Utsunomiya University; Toyohashi University of Technology; Kyoto University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0510-2
• 发表日期: 2005
• 页码: 167-183
• 关键词: network; cut; connectivity; trees

摘要

Given a system (V, T, f, k), where V is a finite set, T subset of or equal to V, f : 2(V) --> R is a submodular function and k greater than or equal to 2 is an integer, the general multiway partition problem (MPP) asks to find a k-partition P = {V-1, V-2,..., V-k} of V that satisfies V-i boolean AND T not equal empty set for all i and minimizes f (V-1) + f (V-2)+...+ f (V-k), where P is a k-partition of V if ( i) V-i not equal empty set, (ii) V-i boolean AND V-j = empty set, i not equal j, and (iii) V-1 boolean OR V-2 boolean OR ... V-k = V hold. MPP formulation captures a generalization in submodular systems of many NP-hard problems such as k-way cut, multiterminal cut, target split and their generalizations in hypergraphs. This paper presents a simple and unified framework for developing and analyzing approximation algorithms for various MPPs.