Fractional 0–1 programming and submodularity

Autor:	Shaoning Han, Andrés Gómez, Oleg A. Prokopyev
Rok vydání:	2022
Předmět:	Control and Optimization Optimization and Control (math.OC) Applied Mathematics FOS: Mathematics Business Management and Accounting (miscellaneous) Management Science and Operations Research Mathematics - Optimization and Control Computer Science Applications
Zdroj:	Journal of Global Optimization. 84:77-93
ISSN:	1573-2916 0925-5001
DOI:	10.1007/s10898-022-01131-5
Popis:	In this note we study multiple-ratio fractional 0--1 programs, a broad class of NP-hard combinatorial optimization problems. In particular, under some relatively mild assumptions we provide a complete characterization of the conditions, which ensure that a single-ratio function is submodular. Then we illustrate our theoretical results with the assortment optimization and facility location problems, and discuss practical situations that guarantee submodularity in the considered application settings. In such cases, near-optimal solutions for multiple-ratio fractional 0--1 programs can be found via simple greedy algorithms.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::67a7921efeab0fe743cc3b6dd2921fb2 https://doi.org/10.1007/s10898-022-01131-5 Zobrazit plný text záznamu Full text from SpringerLink