The maximization of submodular functions : old and new proofs for the correctness of the dichotomy algorithm
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 of creation:||1999|
|Date of revision:|
|Contact details of provider:|| Postal: |
Phone: +31 50 363 7185
Fax: +31 50 363 3720
Web page: http://som.eldoc.ub.rug.nl/
More information through EDIRC
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Boris Goldengorin & Gerard Sierksma & Gert A. Tijssen & Michael Tso, 1999. "The Data-Correcting Algorithm for the Minimization of Supermodular Functions," Management Science, INFORMS, vol. 45(11), pages 1539-1551, November.
- Beasley, J. E., 1993. "Lagrangean heuristics for location problems," European Journal of Operational Research, Elsevier, vol. 65(3), pages 383-399, March.
When requesting a correction, please mention this item's handle: RePEc:dgr:rugsom:99a17. See general information about how to correct material in RePEc.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Joke Bulthuis)
If references are entirely missing, you can add them using this form.