Back

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.

, 33 pages

Research Axis

Research applications

Publication

and
Aleskerov, Fuad; Goldengorin, Boris; Pardalos, Panos M. (Eds.), Clusters, Orders, and Trees: Methods and Applications, Springer Optimization and its Applications Series, 92, Springer, 13–50, 2014 BibTeX reference