کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421400 | 684216 | 2008 | 8 صفحه PDF | دانلود رایگان |
This paper deals with maximization of set functions defined as minimum values of monotone linkage functions. In previous research, it has been shown that such a set function can be maximized by a greedy type algorithm over a family of all subsets of a finite set. In this paper, we extend this finding to meet-semilattices.We show that the class of functions defined as minimum values of monotone linkage functions coincides with the class of quasi-concave set functions. Quasi-concave functions determine a chain of upper level sets each of which is a meet-semilattice. This structure allows development of a polynomial algorithm that finds a minimal set on which the value of a quasi-concave function is maximum. One of the critical steps of this algorithm is a set closure. Some examples of closure computation, in particular, a closure operator for convex geometries, are considered.
Journal: Discrete Applied Mathematics - Volume 156, Issue 4, 15 February 2008, Pages 492–499