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


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