Bibliographic Details
| Title: |
A Characterization of Simultaneous Optimization, Majorization, and (Bi-)Submodular Polyhedra. |
| Authors: |
Schoot Uiterkamp, Martijn H. H.1 (AUTHOR) m.h.h.schootuiterkamp@tilburguniversity.edu |
| Source: |
Mathematics of Operations Research. Feb2025, Vol. 50 Issue 1, p252-276. 25p. |
| Subject Terms: |
*Resource allocation, Greedy algorithms, Polyhedra, Generalization, Motivation (Psychology) |
| Abstract: |
Motivated by resource allocation problems (RAPs) in power management applications, we investigate the existence of solutions to optimization problems that simultaneously minimize the class of Schur-convex functions, also called least-majorized elements. For this, we introduce a generalization of majorization and least-majorized elements, called (a, b)-majorization and least (a, b)-majorized elements, and characterize the feasible sets of problems that have such elements in terms of base and (bi-)submodular polyhedra. Hereby, we also obtain new characterizations of these polyhedra that extend classical characterizations in terms of optimal greedy algorithms from the 1970s. We discuss the implications of our results for RAPs in power management applications and derive a new characterization of convex cooperative games and new properties of optimal estimators of specific regularized regression problems. In general, our results highlight the combinatorial nature of simultaneously optimizing solutions and provide a theoretical explanation for why such solutions generally do not exist. [ABSTRACT FROM AUTHOR] |
|
Copyright of Mathematics of Operations Research is the property of INFORMS: Institute for Operations Research & the Management Sciences and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Business Source Complete |
|
Full text is not displayed to guests. |
Login for full access.
|
