论文标题
分数为0-1编程和次二个
Fractional 0-1 programming and submodularity
论文作者
论文摘要
在本说明中，我们研究多比率分数0-1个程序，这是一类NP-HARD组合优化问题。特别是，在某些相对温和的假设下，我们提供了条件的完整表征，这确保单比率是子模具。然后，我们通过分类优化和设施位置问题来说明我们的理论结果，并讨论确保所考虑的应用程序设置中的次数的实际情况。在这种情况下，可以通过简单的贪婪算法找到多比率分数0-1程序的近乎最佳的解决方案。
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.
