# Fractional 0-1 programming and submodularity

arXiv: https://arxiv.org/abs/2012.07235 · HTML: https://mlsanity.com/paper/2012.07235/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2020.

## Built on by (most cited first, 1 of 1)

- [Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model](https://mlsanity.com/paper/2407.18532/) (2024)

## Abstract (arXiv)

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.