A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering

Pierre Hansen (pierre.hansen@gerad.ca) and Christophe Meyer (christophe.meyer@gerad.ca)
Additional contact information
Pierre Hansen: GERAD, HEC Montréal
Christophe Meyer: GERAD, HEC Montréal

A chapter in Clusters, Orders, and Trees: Methods and Applications, 2014, pp 13-50 from Springer

Abstract: Abstract We derive conditions on the functions φ $$\varphi$$ , ρ, v and w such that the 0–1 fractional programming problem max x ∈ { 0 ; 1 } n φ ∘ v ( x ) ρ ∘ w ( x ) $$\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 Φ ( λ ) = max x ∈ { 0 ; 1 } n v ( x ) − λ w ( x ) $$\Phi (\lambda ) =\max \limits _{x\in \{0;1\}^{n}}v(x) -\lambda w(x)$$ on [0; +∞). In particular we show that when φ $$\varphi$$ 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 max x ∈ { 0 ; 1 } n v ( x ) w ( x ) $$\max \limits _{x\in \{0;1\}^{n}} \frac{v(x)} {w(x)}$$ , and this even if φ $$\varphi$$ and ρ are non-rational 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.

Keywords: 0–1 fractional programming; Submodular function; Polynomial algorithm; Composite functions; Additive clustering (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations: View citations in EconPapers (1)

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4939-0742-7_2

Ordering information: This item can be ordered from
http://www.springer.com/9781493907427

DOI: 10.1007/978-1-4939-0742-7_2

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).