Quasi-Concave Functions and Greedy Algorithms

Many combinatorial optimization problems can be formulated as: for a given set system over E (i.e., for a pair (E, ) where ⊆ 2 is a family of feasible subsets of finite set E), and for a given function F : →R, find an element of for which the value of the function F is minimum or maximum. In general, this optimization problem is NP-hard, but for some specific functions and set systems the problem may be solved in polynomial time. For instance, greedy algorithms may optimize linear objective functions over matroids [11] and Gaussian greedoids [5], [15], [32], while bottleneck objective functions can be maximized over general greedoids [16]. A generalization of greedoids in the context of dynamic programming is discussed in [1] and [2]. Another example is about set functions defined as minimum values of monotone linkage functions. These functions are known as quasi-concave set functions. Such a set function can be maximized by a greedy type algorithm over the family of all subsets of E [19],[24],[29],[30],[34], over antimatroids and convex geometries [17], [20], [25], joinsemilattices [28] and meet-semilattices [21]. A relationship was also established between submodular and quasi-concave functions [28] that allowed to build series of branch and bound procedures for finding maximum of submodular functions. Originally, quasi-concave set functions were considered [23] on the Boolean 2E