A Multilevel Search Algorithm for the Maximization of Submodular Functions

Boris Goldengorin and Diptesh Ghosh ()

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

Abstract: We consider the objective function of a simple recourse problem with fixed technology matrix and integer second-stage variables. Separability due to the simple recourse structure allows to study a one-dimensional version instead. Based on an explicit formula for the objective function, we derive a complete description of the class of probability density functions such that the objective function is convex. This result is also stated in terms of random variables. Next, we present a class of convex approximations of the objective function, which are obtained by perturbing the distributions of the right-hand side parameters. We derive a uniform bound on the absolute error of the approximation. Finally, we give a representation of convex simple integer recourse problems as continuous simple recourse problems, so that they can be solved by existing special purpose algorithms

Date: 2004
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/288251229 (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden (http://irs.ub.rug.nl/ppn/288251229 [302 Found]--> https://irs.ub.rug.nl/ppn/288251229 [302 Found]--> https://www.rug.nl/research/portal/publications/pub(7e60336d-f7aa-4b2f-bced-757dc2fbdeb7).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/pub(7e60336d-f7aa-4b2f-bced-757dc2fbdeb7).html [301 Moved Permanently]--> https://research.rug.nl/en/publications/a-multilevel-search-algorithm-for-the-maximization-of-submodular--3)

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:04a20

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 ().