# Polynomial algorithm for $k$-partition minimization of monotone submodular function

@article{Hidaka2018PolynomialAF, title={Polynomial algorithm for \$k\$-partition minimization of monotone submodular function}, author={Shohei Hidaka}, journal={arXiv: Optimization and Control}, year={2018} }

For a fixed $k$, this study considers $k$-partition minimization of submodular system $(V, f)$ with a finite set $V$ and symmetric submodular function $f: 2^{V} \mapsto \mathbb{R}$. Our algorithm uses the Queyranne's (1998) algorithm for 2-partition minimization which arises at each step of the recursive decomposition of subsets of the original $k$-partition minimization. We show that the computational complexity of this minimizer is $O(n^{3(k-1)})$.

#### One Citation

Fast and exact search for the partition with minimal information loss

- Mathematics, Computer Science
- PloS one
- 2018

A computationally efficient search to precisely identify the Minimum Information Partition among all possible partitions is proposed by exploiting the submodularity of the measure of information loss, when the measureof information loss is submodular. Expand

#### References

SHOWING 1-5 OF 5 REFERENCES

Divide-and-Conquer Algorithms for Partitioning Hypergraphs and Submodular Systems

- Mathematics, Computer Science
- ISAAC
- 2009

The submodular system k-partition problem is a problem of partitioning a given finite set V into k non-empty subsets V 1,V 2, ...,V k so that $\sum_{i=1}^k f(V_i)$ is minimized where f is a… Expand

Minimizing symmetric submodular functions

- Mathematics, Computer Science
- Math. Program.
- 1998

We describe a purely combinatorial algorithm which, given a submodular set functionf on a finite setV, finds a nontrivial subsetA ofV minimizingf[A] + f[V ∖ A]. This algorithm, an extension of the… Expand

Information Theoretical Analysis of Multivariate Correlation

- Mathematics, Computer Science
- IBM J. Res. Dev.
- 1960

The present paper gives various theorems, according to which Ctot(λ) can be decomposed in terms of the partial correlations existing in subsets of λ, and of quantities derivable therefrom. Expand

The Multiinformation Function as a Tool for Measuring Stochastic Dependence

- Computer Science, Mathematics
- Learning in Graphical Models
- 1998

It is argued that the corresponding multiinformation function is a useful tool for problems concerning stochastic (conditional) dependence and independence (at least in the discrete case). Expand

Fast and exact search for the partition with minimal information loss

- Mathematics, Computer Science
- PloS one
- 2018

A computationally efficient search to precisely identify the Minimum Information Partition among all possible partitions is proposed by exploiting the submodularity of the measure of information loss, when the measureof information loss is submodular. Expand