2008/08/24 by Yulia Kempner, Kempner, Yulia, Vadim E. Levit +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05B35 (Primary) #90C27 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Search Problems #Peroxisome Proliferator-Activated Receptors #cs.DM #math.CO #msc:05B35 #msc:90C27
paper · pdf · doi:10.48550/arxiv.0808.3244
12 pages, 2 figures
arxiv created 2008/08/24 · openalex publication_date 2008/08/24 · arxiv updated 2011/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A function F defined on 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, theory of graph, data mining, clustering and other fields. The maximization of quasi-concave function takes, in general, exponential time. However, if a quasi-concave function is defined by associated monotone linkage function then it can be optimized by the greedy type algorithm in a polynomial time. 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 & Levit, 2003). 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.