Duality between quasi-concave functions and monotone linkage functions - Mathematics > CombinatoricsReportar como inadecuado




Duality between quasi-concave functions and monotone linkage functions - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: A function $F$ defined on all subsets of a finite ground set $E$ isquasi-concave if $FX\cup Y\geq\min\{FX,FY\}$ for all $X,Y\subset E$.Quasi-concave functions arise in many fields of mathematics and computerscience such as social choice, theory of graph, data mining, clustering andother fields.The maximization of quasi-concave function takes, in general, exponentialtime. However, if a quasi-concave function is defined by associated monotonelinkage function then it can be optimized by the greedy type algorithm in apolynomial time.Quasi-concave functions defined as minimum values of monotone linkagefunctions were considered on antimatroids, where the correspondence betweenquasi-concave and bottleneck functions was shown Kempner and Levit, 2003. Thegoal of this paper is to analyze quasi-concave functions on different familiesof sets and to investigate their relationships with monotone linkage functions.



Autor: Yulia Kempner, Vadim E. Levit

Fuente: https://arxiv.org/







Documentos relacionados