G-2012-79
A Polynomial Algorithm for a Class of 0-1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering
and BibTeX reference
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