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

Pierre Hansen () and Christophe Meyer ()
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 () and Springer Nature Abstracting and Indexing ().