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 φ
, ρ
, v
and w
such that the 0-1 fractional programming problemmax
\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