𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the minimization of symmetric and general submodular functions

✍ Scribed by H Narayanan

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
131 KB
Volume
131
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we relate the minimization problems for general submodular functions and symmetric submodular functions. We characterize the contractions and restrictions of symmetric submodular functions. The latter we show to be the same as posimodular functions. Finally, we prove the equivalence of various symmetric submodular function minimization problems and the general submodular function minimization problem. We also give a preprocessing algorithm for the general submodular function minimization problem which could lead to substantial size reduction.

πŸ“œ SIMILAR VOLUMES

Minimal Factorizations of a Cycle and Ce
Minimal Factorizations of a Cycle and Central Multiplicative Functions on the Infinite Symmetric Group
✍ Philippe Biane πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 508 KB

We show that the number of factorizations \_=/ 1 } } } / r of a cycle of length n into a product of cycles of lengths a 1 , ..., a r , with r j=1 (a j &1)=n&1, is equal to n r&1 . This generalizes a well known result of J. Denes, concerning factorizations into a product of transpositions. We investi

On the positivity of symmetric polynomia
On the positivity of symmetric polynomial functions.: Part I: General results
✍ Vlad Timofte πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 177 KB

We prove that a real symmetric polynomial inequality of degree d 2 holds on R n + if and only if it holds for elements with at most d/2 distinct non-zero components, which may have multiplicities. We establish this result by solving a Cauchy problem for ordinary differential equations involving the

A Markov chain on the symmetric group an
A Markov chain on the symmetric group and Jack symmetric functions
✍ Phil Hanlon πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 872 KB

Hanlon, P., A Markov chain on the symmetric group and Jack symmetric functions, Discrete Mathematics 99 (1992) 123-140. Diaconis and Shahshahani studied a Markov chain Wf(l) whose states are the elements of the symmetric group S,. In W,(l), you move from a permutation n to any permutation of the for