Duality between quasi-concave functions and monotone linkage functions

A function F defined on the family of all subsets of a finite ground set E is quasi-concave, if F(X∪Y)≥min{F(X),F(Y)} for all X,Y⊆E. Quasi-concave functions arise in many fields of mathematics and computer science such as social choice, graph theory, data mining, clustering and other fields. The maximization of a quasi-concave function takes, in general, exponential time. However, if a quasi-concave function is defined by an associated monotone linkage function, then it can be optimized by a greedy type algorithm in polynomial time. Recently, quasi-concave functions defined as minimum values of monotone linkage functions were considered on antimatroids, where the correspondence between quasi-concave and bottleneck functions was shown Kempner and Levit (2003) 6]. The goal of this paper is to analyze quasi-concave functions on different families of sets and to investigate their relationships with monotone linkage functions.