The maximization of submodular functions: old and new proofs for the correctness of the dichotomy algorithm

Boris Goldengorin, Gert A. Tijssen and Michael Tso
Additional contact information
Michael Tso: Groningen University

No 99A17, Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management)

Abstract: The first purpose of this paper is to make an old (Russian) theoretical results about the structure of local and global maxima of submodular functions, Cherenin’s excluding rules and his Dichotomy Algorithm more accessible for Western community. The second purpose of this paper is to present our main result which can be stated as follows. For any pair of embedded subsets, the difference of their function values is a lower bound for the difference between the unknown(!) optimal values of the corresponding partition defined by these subsets. A simple justification of Cherenin’s rules, the Dichotomy Algorithmand its generalization with the new branching rules from our main result are presented. The usefulness of our new branching rules is illustrated by means of a numerical example.

Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://irs.ub.rug.nl/ppn/183932617 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (http://irs.ub.rug.nl/ppn/183932617 [302 Found]--> https://irs.ub.rug.nl/ppn/183932617 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(1a85c613-f249-4727-bf15-8981944df9e8).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(1a85c613-f249-4727-bf15-8981944df9e8).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/the-maximization-of-submodular-functions-old-and-new-proofs-for-t-2)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gro:rugsom:99a17

Access Statistics for this paper

More papers in Research Report from University of Groningen, Research Institute SOM (Systems, Organisations and Management) Contact information at EDIRC.
Bibliographic data for series maintained by Hanneke Tamling ().