### G-2012-79

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

## Pierre Hansen and 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.

Published **December 2012**
,
33 pages