Minimizing symmetric submodular functions

Minimizing symmetric submodular functions

0.00 Avg rating—0 Votes
Article ID: iaor2000492
Country: Netherlands
Volume: 82
Issue: 1/2
Start Page Number: 3
End Page Number: 12
Publication Date: Jun 1998
Journal: Mathematical Programming
Authors:
Keywords: combinatorial analysis
Abstract:

We describe a purely combinatorial algorithm which, given a submodular set function f on a finite set V, finds a nontrivial subset A of V minimizing f[A] + f[V\A]. This algorithm, an extension of the Nagamochi–Ibaraki minimum cut algorithm as simplified by Stoer and Wagner and by Frank, minimizes any symmetric submodular function using O(|V|3) calls to a function value oracle.

Reviews

Required fields are marked *. Your email address will not be published.