Name
Abstract | ||
|---|---|---|
Given a system (V,T,f,k) where V is a finite set, T ⊆ V, f : 2V → R is a submodular function and k ≥ 2 is an integer, the multiway partition problem (MPP) asks to find a k-partition P = {V1, V2,...,Vk} of V that satisfies Vi ∩ T ≠ 0 for all i and minimizes f(V1) + f(V2)+...+f(Vk). This formulation captures a generalization of many NP-hard partition problems in graphs or hypergraphs. Previously, the authors have shown a simple framework for approximating MPPs by greedily increasing the size of partition by one. In this paper, we show that, if T = V, improved guarantees are available by greedily increasing the size by two. We also show polynomial time implementations for several problem classes. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/j.dam.2003.10.007 | Discrete Applied Mathematics |
Keywords | Field | DocType |
polynomial time implementation,submodular function,multiway partition problem,problem class,k -way cut,finite set,improved guarantee,multiterminal cut,approximating mpps,np-hard partition problem,k-partition p,approximation algorithm,generalized greedy splitting algorithm,simple framework,satisfiability,polynomial time | Partition problem,Integer,Discrete mathematics,Approximation algorithm,Combinatorics,Hypergraph,Algorithm,Submodular set function,Greedy algorithm,Partition (number theory),Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
143 | 1-3 | Discrete Applied Mathematics |
Citations | PageRank | References |
5 | 0.46 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Liang Zhao | 1 | 131 | 24.39 |
| Hiroshi Nagamochi | 2 | 1513 | 174.40 |
| Toshihide Ibaraki | 3 | 2593 | 385.64 |