Groupe d’études et de recherche en analyse des décisions

A Polynomial Algorithm for a Class of 0-1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering

Pierre Hansen et Christophe Meyer

We derive conditions on the functions $$\varphi$$, $$\rho$$, $$v$$ and $$w$$ such that the 0-1 fractional programming problem$$\max\limits_{x\in \{0;1\}^n}$$ $$\frac{\varphi \circ v(x)}{\rho \circ w(x)}$$ can be solved in polynomial time by enumerating the breakpoints of the piecewise linear function $$\Phi(\lambda) = \max\limits_{x\in \{0;1\}^n} v(s)-\lambda w(x)$$ on $$[0; +\infty)$$. In particular we show that when $$\varphi$$ is convex and increasing, $$\rho$$ is concave, increasing and strictly positive, $$v$$ and $$-w$$ are supermodular and either $$v$$ or $$w$$ has a monotonicity property, then the 0-1 fractional programming problem can be solved in polynomial time in essentially the same time complexity than to solve the fractional programming problem $$\max\limits_{x\in \{0;1\}^n}$$ $$\frac{v(x)}{w(x)}$$, and this even if $$\varphi$$ and $$\rho$$ are nonrational functions provided that it is possible to compare efficiently the value of the objective function at two given points of $$\{0;1\}^n$$. We apply this result to show that a 0-1 fractional programming problem arising in additive clustering can be solved in polynomial time.

, 33 pages