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

We derive conditions on the functions φ $$\varphi$$ , ρ, v and w such that the 0–1 fractional programming problem max x ∈ { 0 ; 1 } n φ ∘ v ( x ) ρ ∘ w ( x ) $$\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 Φ ( λ ) = max x ∈ { 0 ; 1 } n v ( x ) − λ w ( x ) $$\Phi (\lambda ) =\max \limits _{x\in \{0;1\}^{n}}v(x) -\lambda w(x)$$ on [0; +∞). In particular we show that when φ $$\varphi$$ is convex and increasing, ρ 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 x ∈ { 0 ; 1 } n v ( x ) w ( x ) $$\max \limits _{x\in \{0;1\}^{n}} \frac{v(x)} {w(x)}$$ , and this even if φ $$\varphi$$ and ρ are non-rational 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.