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 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.

, 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