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 problemmaxx∈{0;1}n
φ∘v(x)ρ∘w(x)
can be solved in polynomial time by enumerating the breakpoints of the piecewise linear function Φ(λ)=maxx∈{0;1}nv(s)−λw(x)
on [0;+∞)
. In particular we show that when φ
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 maxx∈{0;1}n
v(x)w(x)
, and this even if φ
and ρ
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